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

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

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

Сотрудники
Номер	ФИО		Отдел		Должность		Оклад
1	Иванов А.А.		торговый		менеджер		7000
2	Сидоров Н.П.		плановый		экономист		5000
3	Сидорова М.И.		торговый		зав.складом		6000
4	Ольгина Н.А.		плановый		экономист		5500
5	Горев С.В.		плановый		зав.отделом		10000
Комнаты
НомерСотрудника		Этаж		НомерКомнаты
3		2		17
1		2		17
7		2		18
5		3		7
2		3		27

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

Каждому отношению базы данных со схемой 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 в сигнатуре базы данных определяет множество состояний, т.е. наборов значений ее свободных переменных, на которых она истинна. Такое множество наборов можно рассматривать как множество кортежей, которые входят в новое отношение  , определяемое формулой 

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

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

ФИО	НомерКомнаты
Сидоров Н.П.	27
Горев С.В.	7

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