Модели логической организации данных

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

В основу реляционной модели данных [41, 73, 74] положено понятие отношения. Подмножество R С D х ?>2 х • • • х D_n есть отношение арности п с доменами Дг,…, D_n. Рассматриваемые отношения, как правило, конечные, поэтому удобно представлять их в виде плоских таблиц. Строки таблицы называются кортежами, а столбцы — атрибутами. Подмножество атрибутов отношения называется ключом, если проекция таблицы на это множество состоит из разных строк, но удаление любого атрибута из ключа нарушает это свойство. Понятие ключа соответствует тупиковому тесту, поэтому результаты, полученные в теории тестов (А.Е.Андреев [3, 4, 5], А. Д. Коршунов [30], В. Н. Носков [44, 45, 46], Г. Р. Погосян [49] и др.) могут быть использованы для оценки мощности ключа и минимального числа атрибутов в ключе. Оценивались мощности ключей в случайных БД (таблицах) (О.Б.Селезнев, Б. Тальхайм [55] и др.). Реляционная БД — это множество таблиц, обогащенное операциями объединения, пересечения, разности, декартова произведения, проекции, соединения, селекции, частного и др. Изучение этих алгебр отношений составляет содержание теории реляционных БД. Ассоциируемый с табличным представлением способ хранения данных не компактен, а способ поиска — полный перебор. В связи с этим в современных реляционных БД реляционная модель используется только как внешнее представление, то есть представление пользователя, тогда как внутреннее представление данных, то есть представление на машинных носителях, — принципиально другое. Простота представления при сохранении всех функциональных возможностей БД делают реляционную модель удобной для изучения качественных свойств и характеристик БД. Наглядность и простота понимания — причина популярности этой модели среди большинства пользователей.

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

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

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

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

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