База данных

База данных – формализованное представление информации, удобное для хранения и поиска данных в нем. Понятие Б.д. возникло в 60-е годы 20 века и связано с развитием вычислительной техники и информатики. Тематика теории Б.д. связана с поиском удобного представления, компактного хранения, быстрого поиска, защищенности и других свойств данных. Развитию этого направления способствовали как производственные и творческие коллективы: IBM (иерархическая модель данных), Рабочая группа по Б.д. Ассоциации по языкам систем обработки данных – CODASYL (сетевая модель данных), исследовательская группа по системам управления Б.д. Американского национального института стандартов – ANSI/SPARC Study Group on DataBase Management Systems (принципы проектирования Б.д.), так и отдельные исследователи: Кодд (E.F.Codd) (реляционная модель данных), Галлейр (H.Gallaire), Минкер (J.Minker) (дедуктивные Б.д.), Тальхайм (B.Thalheim) (моделирование семантики в Б.д., теория ограничений целостности), Аткинсон (M.Atkinson), Бири (C.Beeri) и др. (объектно-ориентированные Б.д.), В.Н.Решетников (алгебраическая модель информационного поиска), Думи (A.Dumey), А.П.Ершов (методы хеширования), Бентли (J.L.Bentley), Кнут (D.E.Knuth), Ли (D.T.Lee), Маурер (W.D.Maurer), Ульман (J.D.Ullman), Шеймос (M.I.Shamos) и др. (сложность алгоритмов обработки данных), Э.Э.Гасанов (информационно-графовая модель данных, сложность алгоритмов поиска) и многие другие.

Основные виды представления (модели) данных сформировались под влиянием практики с использованием средств математики.

В основу реляционной модели данных[1] положено понятие отношения. Подмножество есть отношение арности n с доменами D₁,D₂...,D_n. Рассматриваемые отношения, как правило, конечные, поэтому удобно представлять их в виде плоских таблиц. Строки таблицы называются кортежами, а столбцы – атрибутами. Подмножество атрибутов отношения называется ключом, если проекция таблицы на это множество состоит из разных строк, но удаление любого атрибута из ключа нарушает это свойство. Понятие ключа соответствует тупиковому тесту, поэтому результаты, полученные в теории тестов (А.Е.Андреев, В.Н.Носков, Г.Р.Погосян и др.) могут быть использованы для оценки мощности ключа и минимального числа атрибутов в ключе. Оценивались мощности ключей в случайных Б.д. (таблицах) (О.Б.Селезнев, Б.Тальхайм и др.). Реляционная Б.д. – это множество таблиц, обогащенное операциями объединения, пересечения, разности, декартова произведения, проекции, соединения, селекции, частного и др. Изучение этих алгебр отношений составляет содержание теории реляционных Б.д. Ассоциируемый с  табличным представлением способ хранения данных не компактен, а способ поиска – полный перебор. В связи с этим в современных реляционных Б.д. реляционная модель используется только как внешнее представление, то есть представление пользователя, тогда как внутреннее представление данных, то есть представление на машинных носителях, – принципиально другое. Простота представления при сохранении всех функциональных возможностей Б.д. делают реляционную модель удобной для изучения качественных свойств и характеристик Б.д. Наглядность и простота понимания – причина популярности этой модели среди большинства пользователей.

Если в табличном представлении произвести лексикографическое упорядочение и сделать склейку по совпадающим префиксам, то получается  древовидное представление данных, в основе которого лежит понятие дерева. Такое представление ведет к большей компактности данных и к ускорению поиска нужных данных. Такие древовидные структуры, как бинарные деревья, 2-3-деревья, В-деревья, сортирующие деревья[2]используются для внутреннего представления данных. Древовидное представление удобно использовать в лингвистических и подобных им Б.д., напр., когда надо найти то или иное слово. В случае поиска множества однокоренных слов, то есть слов с заданной средней частью, древовидное представление не очень удобно. Древовидное представление все еще достаточно просто для понимания, хотя и не так наглядно как табличное. При использовании  древовидной (или иерархической) модели данных как внешнего представления данных предполагаются иерархические отношения между данными, то есть отношения типа родитель-потомки, когда у каждого объекта только один родитель, но может быть несколько потомков. Одной из систем, использующих иерархическую модель данных, является система IMS фирмы IBM[3].

Обобщение понятия дерева до графа аналогично переходу от древовидного к  сетевому представлению данных. При векторном виде данных в древовидном представлении склейка данных может быть сделана только по начальному отрезку; в сетевом представлении она допустима по любым отрезкам. В  сетевой модели данных доступ к данным может быть осуществлен по многим путям. Она позволяет реализовать более широкий класс отношений между объектами, чем древовидная. Эта модель данных развивается ассоциацией CODASYL[4]. Поскольку сетевая модель является обобщением древовидной, то она предоставляет больше возможностей как для описания предметной области, представляемой Б.д., так и для нахождения оптимальных решений хранения и поиска данных. Но использование сетевой модели требует высокой квалификации от разработчика и поэтому она не была воспринята массовым пользователем.

В объектно-ориентированной модели данных[5], опирающейся на принципы объектно-ориентированного программирования, каждый объект представляется как черный ящик, доступ к данным которого осуществляется только через специальные функции, прилагаемые к нему. Из таких ящиков строятся более сложные объекты, которые в свою очередь могут служить новыми ящиками для построения объектов следующего уровня сложности и т.д. Главное преимущество объектно-ориентированной модели – ее технологичность, в связи с чем это одна из наиболее развивающихся моделей сегодня.

Под влиянием математической логики строится  дедуктивная модель данных[6]. Данные в дедуктивных базах данных рассматриваются как аксиомы, а новые данные получаются из аксиом путем логического вывода. Преимущество этой модели – компактность начального множества данных (все зашито в аксиомы и правила вывода) и потенциальная бесконечность множества выводимых фактов. Недостаток – большие ресурсы по времени и памяти, необходимые для процесса вывода. Дедуктивные базы данных удобно использовать в системах принятия решений, когда заранее не очерчена область возможных ситуаций.

Модели данных для описания внутренней (или физической) организации Б.д. имеют дело с размещением данных на запоминающих устройствах. Здесь главным является эффективность функционирования Б.д., то есть обеспечение эффективности поиска, занесения, удаления и компактность хранения данных. При этом требования быстроты вставки, поиска и компактности хранения данных находятся в противоречии. Для быстрого поиска необходимо строить дополнительные сложные структуры данных, которые затрудняют процесс вставки новых данных и не способствуют компактности. Одной из моделей, используемых для исследования сложности алгоритмов, является алгебраическое дерево вычислений (АДВ-модель)[2], с помощью которой получены оценки сложности алгоритмов работы с данными.

Моделью данных, предназначенной для исследования сложностных характеристик алгоритмов работы с данными, является информационно-графовая модель[7] (см.  информационно-графовая модель данных), основывающаяся на теории управляющих систем. В ней структура данных задается ориентированным графом (информационным), ребра и вершины которого нагружены элементами данных и функциями, определенными на множестве запросов. В графе выделена вершина, называемая корнем (входом), вершины графа, нагруженные элементами данных, являются выходами. Кроме структуры информационный граф задает и алгоритм поиска, на вход которого поступает запрос, а на выходе получается множество данных. Процесс поиска начинается с корня и распространяется в зависимости от значений нагрузочных функций, возможно, в разных направлениях. Если этот процесс на графе захватывает элементы данных, то они включаются в ответ алгоритма. Задаются две меры сложности информационных графов. Первая называется объемом и равна количеству ребер графа. Она характеризует объем памяти, необходимый для хранения данных. Вторая мера равна количеству вычисленных функций в процессе порождаемого запросом поиска. Она характеризует время работы алгоритма на запросе. Особенностью этой модели является возможность оценки среднего времени работы алгоритма.

Работа с Б.д. предполагает создание удобных языков –  языков манипулирования данными, – примеры которых доставляют формальные языки логики и алгебры. В алгебраических языках манипулирования данными запрос к Б.д. определяет последовательность операций, которые приведут к ответу. Такими языками являются ISDL и АСТРИД[1][8]. В языках манипулирования данными, основанных на исчислении предикатов, запрос к Б.д. соответствует формуле некоторой формально-логич. теории, а ответом является множество объектов из области интерпретации, на котором истинна формула, соответствующая запросу. Такими языками являются QUEL, SQL, QBE [1,8].

Тематика теории Б.д. связана с двумя основными направлениями. Первое в основном опирается на аппарат формально-логических теорий и связано с изучением качественных свойств моделей данных и их семантическим обоснованием. К этому же направлению относятся вопросы выразительности и сложности языков запросов, соответствующих моделям данных, изучение Б.д. как теорий (например, в интуиционистской логике высшего порядка), а также теория ограничений целостности[9]. В ней изучаются ограничения, накладываемые предметной областью, определяющие связи между компонентами Б.д. и описывающие поведение Б.д. во времени. Ограничения целостности могут быть использованы в качестве языка описания семантики Б.д. Изучаются особого вида ограничения целостности, называемые зависимостями. Они делятся на статические (отражающие семантику всех возможных состояний Б.д.) и динамические (описывающие поведение Б.д. во времени, то есть корректность последовательностей ее состояний). Изучается проблема выводимости некоторой данной зависимость из заданного списка зависимостей. Выделены классы зависимостей, в которых эта проблема неразрешима и P- или NP-разрешима. При разрешимости проблемы выводимости актуальной становится задача об аксиоматизации соответствующего класса зависимостей. Известны случаи аксиоматизируемых и неаксиоматизируемых классов.

Второе основное направление тематики теории Б.д. связано с вопросами сложности алгоритмов обработки данных. Практика выявила несколько типов задач информационного поиска, для эффективной реализации которых было разработано большое количество алгоритмов с разными соотношениями таких характеристик алгоритмов как время работы в худшем случае и в среднем, объем памяти, необходимый алгоритму. Каждый из этих алгоритмов имеет свою структуру хранения данных, и соответствующие ей алгоритмы обновления данных. Среди основных типов задач информационного поиска можно выделить следующие. Задача поиска идентичных объектов, когда в множестве данных надо найти объекты равные запросу. Задача о близости, которая состоит в поиске во множестве, в котором задан линейный порядок, объекта, ближайшего к объекту-запросу. Задача включающего поиска (или дескрипторный поиск, или поиск по ключевым словам), когда запрос задает набор свойств и надо найти объекты, обладающие этими свойствами. Задача о доминировании, которая состоит в поиске в конечном подмножестве n-мерного пространства всех тех точек, которые не больше по каждой из компонент, чем запрос, являющийся в данном случае точкой n-мерного пространства. Задача интервального поиска, которая состоит в поиске в конечном подмножестве n-мерного пространства всех тех точек, которые попадают в n-мерный параллелепипед-запрос.

Для любой задачи информационного поиска справедлива элементарная нижняя оценка сложности, говорящая, что время поиска не меньше чем время перечисления ответа (эта оценка называется мощностной). Для задачи поиска идентичных объектов с помощью деления пополам легко получается логарифмическая верхняя оценка времени поиска в худшем случае, с другой стороны для этой задачи в рамках АДВ-модели получена логарифмическая нижняя оценка времени поиска в худшем случае (теоретико-информационная нижняя оценка сложности,  A. B. Borodin). С помощью методов хеширования получены алгоритмы поиска идентичных объектов, для которых доказано ( А. П. Ершов), что в среднем время поиска равно константе, но в худшем случае эти алгоритмы равны перебору, то есть имеют линейную сложность. Аналогичные результаты получаются для задачи о близости. Задачу о доминировании и задачу интервального поиска относят также к направлению, называемому  вычислительная геометрия и посвященному исследованию сложности алгоритмов решения геометрических задач. По задаче интервального поиска получены следующие результаты. Бентли (J.L.Bentley) предложил метод многомерного двоичного дерева (k-D-дерева), который имеет линейные затраты по памяти, но в худшем случае двумерная задача решается этим алгоритмом за время . Здесь и далее, k равно мощности множества данных, а оценки приводятся без времени перечисления ответа. Далее Бентли предложил метод прямого доступа, оторый решает задачу за время , но требует затрат по памяти порядка k³ для двумерной задачи. Чтобы уменьшить требуемую память Бентли и Маурером (W.D.Maurer), был предложен многоэтапный метод прямого доступа. Он позволяет снижать порядок требуемой памяти, но при этом возрастает константа при логарифме в оценке времени. С помощью метода дерева интервалов (или дерева регионов) Бентли и Шеймос (M.I.Shamos) получили оценку времени поиска при затратах памяти , где  n– размерность задачи интервального поиска. Уиллард (D.E.Willard) и Люкер (G.S.Lueker) независимо предложили модификацию дерева интервалов, которая позволила снизить время поиска до при тех же затратах памяти. Чазелле (B.M.Chazelle) для двумерной задачи смог снизить затраты памяти до , но при этом возросла константа при логарифме в оценке времени. Во всех этих работах оценивается время поиска в худшем случае.

Информационно-графовая модель позволяет взглянуть на эту разрозненную картину с единых позиций. Во-первых, если  Х– множество символов запросов с заданным на нем вероятностным пространством , где  – алгебра подмножеств множества Х, P – вероятностная мера на ;  Y– множество символов данных (записей);  – бинарное отношение на X х Y, называемое отношением поиска; то тройка  называется  типом. Тройка , где V – некоторое конечное подмножество множества Y, называется задачей информационного поиска (ЗИП) типа S. Содержательно ЗИП   состоит в перечислении для произвольно взятого запроса всех и точно тех записей , что . Так, например, тип n-мерной задачи о доминировании описывается тройкой , где   задается соотношением Во-вторых, каждая ЗИП   задает множество предикатов на  X

Тогда задача построения хорошего алгоритма поиска, решающего данную ЗИП, сводится к построению схемы, реализующей как функции проводимости функции из множества , где в качестве схем удобно рассматривать информационные графы. После введения сложности схемы мы получаем стандартную для теории синтеза управляющих систем постановку: по заданной системе функций (задаваемой ЗИП) построить схему (информационный граф), реализующую эту систему функций и имеющую минимальную сложность. Таким образом, информационно-графовая модель позволяет решать вопросы построения хороших алгоритмов поиска методами теории управляющих систем. В рамках информационно-графовой модели получены следующие результаты. Для задачи поиска идентичных объектов и задачи о близости получены константные по времени в среднем и при этом логарифмические по времени в худшем случае и линейные по памяти алгоритмы поиска. Также получены алгоритмы, константные по времени в худшем случае при квадратичных затратах памяти. Для задачи включающего поиска получена нижняя оценка среднего времени поиска в два раза лучшая, чем мощностная нижняя оценка. Кроме того, доказано существование задач включающего поиска, для которых эта нижняя оценка асимптотически не улучшаема. Для задач о доминировании и интервального поиска получены алгоритмы, средняя сложность по времени которых отличается от мощностной нижней оценки на константу. Также разработана модификация алгоритма Бентли-Маурера, сохраняющая порядки времени поиска в худшем случае и объема памяти при снижении среднего времени поиска (без времени перечисления ответа) до константы. Представляется, что данное направление исследований является точкой роста теории Б.д.

Специальное направление в теории Б.д. составляет защищенность данных от случайного или преднамеренного доступа к ним несанкционированных пользователей. Интенсивное развитие всемирной компьютерной сети Internet делает это направление особенно актуальным (см.  защита информации).

Литература