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

Большинство современных промышленных баз данных являютсяреляционными - данные в них представляют конечные отношения(relations), которые хранятся в таблицах. Схема отношения R(A₁,A₂, ..., A_n)включает имя отношения R и список его атрибутов A₁,A₂, ..., A_n. Вообще говоря, атрибуты в схеме отношения считаются неупорядоченными, т.е. являются не списком, а множеством. Но мы будем считать, что их порядок в схеме является "стандартным". Для каждого атрибута A_i определено множествоdom(A_i) его допустимых значений. Схема базы данных состоит из перечня схем отношений, входящих в эту базу. В приложенияхотношения чаще называют таблицами, их атрибуты -столбцами, строки таблиц - кортежамиили записями, а их элементы - полями. В каждый момент времени состояние базы данных (ее экземпляр) - это набор (конечных) таблиц имеющих соответствующие схемы.

Пример 8.1. Пусть, например, база данных со сведениями о сотрудниках некоторой организации имеет схему: Сотрудники(Номер, ФИО, Отдел, Должность, Оклад), Комнаты(НомерСотрудника, Этаж, НомерКомнаты). Рассмотрим некоторый экземпляр этой базы данных.

С точки зрения логики предикатов, этот экземпляр не что иное, как некоторая конечная система сигнатуры с основным множеством, включающим строки и числа из таблиц. Первая из приведенных таблиц задает интерпретацию предиката Сотрудники⁽⁵⁾, а вторая - интерпретацию предиката Комнаты⁽³⁾.

Каждому отношению базы данных со схемой R(A₁, ..., A_n) мы сопоставим n -местный предикат с тем же именем и n одноместных предикатов A_i(x) (i=1, ..., n), выражающих принадлежность объекта xобласти dom(A_i) допустимых значений атрибута A_i. Следовательно, кортеж (a₁, ... , a_n)принадлежит отношению R тогда и только тогда, когда истинна формула . Множество таких предикатов для всех отношений базы данных и стандартных отношений, определенных на областях ее атрибутов (обычно это отношенияравенства и порядка: =, <, <=, >, >= ), образуют сингатуру базы данных.

Например, для приведенного выше отношения Сотрудники⁽⁵⁾ предикаты-свойства соответствующих областей значений могут быть заданы следующим образом:

• - целое число,
• - строка символов длины <= 30,
• ,
• - строка символов длины <= 80,
• - целое число в интервале от 1000 до 100 000.

Каждый кортеж отношения Сотрудники удовлетворяет формуле .

Ниже мы будем просто писать R(a₁, ... , a_n), подразумевая, что значения a_i входят в соответствующие области dom(A_i). Каждая формула со свободными переменными x₁, ... , x_k в сигнатуре базы данных определяет множество состояний, т.е. наборов значений ее свободных переменных, на которых она истинна. Такое множество наборов можно рассматривать как множество кортежей, которые входят в новое отношение , определяемое формулой

Например, формула

задает отношение , определяющее список комнат сотрудников планового отдела:

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