10. ДЕДУКТИВНЫЕ БАЗЫ ДАННЫХ

В настоящей главе рассмотрены некоторые аспекты теории дедуктивных баз данных, запросы к которым удовлетворяются на основе использования исчислений.

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

10.1. Реляционные базы данных

Данные в реляционных базах хранятся в виде таблиц, задающих определенные отношения между этими данными. Каждому столбцу таблицы взаимно однозначно соответствует атрибут (имя столбца) а атрибуту — множество значений переменных Переменные одного и того же множества принимают значения из одного универсума. Множество значений переменных называют доменом.

Под схемой отношений подразумевают выражение в котором а является именем схемы отношений, термы базы, . Схему отношений, все термы которой конкретизированы называют конкретизированной схемой отношений гили таблицей Если нас не интересуют конкретные множества переменных и доменов, то схему отношений обозначают , а соответствующую ей таблицу

База данных — это множество конкретизированных схем отношений или таблиц, называемых также конкретизацией, или состоянием базы. Состояние базы, т.е. ее конкретизация, может изменяться. Множество всех атрибутов базы есть где — количество атрибутов. Подмножество атрибутов множества А, состоящее из атрибутов, индексы которых пробегают множество значений обозначим Будем полагать, что атрибуты всегда упорядочены в соответствии с порядком индексов в множестве упорядочено по возрастанию. Таким образом, Множество будем называть основой схемы отношений. В каждом состоянии базы данных каждому атрибуту соответствует один домен из некоторого конечного множества всех доменов Соответствие между множеством атрибутов о и доменов в каждом состоянии базы данных можно выразить в виде функции отображающей множество атрибутов на множество доменов, т. е. Символ состояния базы данных будем, как правило, опускать, имея в виду, что база всегда конкретизирована, т. е. имеет состояние.

Множество всех различных подмножеств индексов где содержащих различных индексов из множества индексов всех атрибутов, обозначают где — количество сочетаний из по С учетом введенных обозначений схему отношений можно обозначить как Обозначим

Здесь X — знак операции декартова произведения всех доменов, атрибуты которых принадлежат множеству

Строкой таблицы где называют упорядоченное множество (кортеж) Конкретный элемент строки лежащий на пересечении ее со столбцом, соответствующим атрибуту а, обозначим Множество всех строк таблицы обозначим

Пример. Заладим конкретизированную схему отношений для данных о поездах, следующих из начальных до конечных пунктов в центральной России. Эту схему отношений назовем прямые маршруты. Введем для нее атрибуты номерпоезда, пункт отправления, пункт назначения, день_отправления, время отправления и соответствующие им домены:

Конкретизированную схему отношений прямые маршруты можно представить в виде таблицы (табл. 2.1).

Таблица 2.1