egorius | История SQL. 4. Реляционное исчисление

Начало: 1. Необходимая предыстория, назад: 3. Реляционная алгебра.

Если реляционная алгебра более или менее привычна (что не удивительно, поскольку SQL в основном базируется именно на ней), то с исчислением дело обстоит хуже. Реляционное исчисление основано не на теории множеств, а на другом формализме — логике предикатов первого порядка. Впервые Кодд подробно описал его в работе 1972 года, хотя и упоминал с самой первой статьи.

Логика предикатов корнями уходит в труды Аристотеля (а это IV век до н. э), который пытался свести рассуждения об истинности любого предположения к формальным правилам вывода новых фактов из имеющихся (силлогизмы Аристотеля).

В нынешнем понимании, логика предикатов имеет дело со следующими объектами. Во-первых, с константами и переменными. Во-вторых, с предикатами, под которыми понимаются булевские (т. е. принимающие истинное или ложное значение) функции, аргументами которых могут выступать константы и переменные. В-третьих, предикаты объединяются в выражения с помощью логических связок: и (∧), или (∨), не (¬).

Предикаты связаны с отношениями вот как. Возьмем какое-нибудь отношение, допустим, V. Неформальный смысл этого отношения можно определить так: «vendor# — поставщик с именем vendor_name». Но чтобы точно задать отношение, мы должны явно перечислить всех поставщиков и их имена. Можно считать, что отношение содержит множество истинных утверждений-кортежей: если (x, y) входит в отношение, то x — поставщик с именем y. Что, если (x, y) не входит в отношение? Тогда мы принимаем предположение о замкнутости мира и считаем, что такого поставщика нет в природе. Предикат, соответствующий отношению, показывает истинность утверждения («является ли vendor# поставщиком с именем vendor_name?»): он принимает истинное значение тогда и только тогда, когда его единственный параметр-кортеж входит в соответствующее отношение.

Предикаты-отношения я для удобства буду обозначать той же буквой, что и само отношение. Например, V(x) означает, что переменная x принимает значение из множества кортежей отношения V.

Кроме предикатов-отношений Кодд включил в реляционное исчисление и обычные бинарные предикаты сравнения (равно, больше и т. п.) для использования с атрибутами кортежей. К атрибутам можно обратиться, используя индекс: x[1] обозначает первый атрибут V.

Далее, если выражение содержит свободную переменную, то об истинности такого выражения нельзя судить, пока переменная не будет связана одним из двух кванторов:

существования — ∃x (P) означает «найдется такой x, что верно P»,
всеобщности — ∀x (P) означает «для любого x верно P».

Теперь можно сказать о том, почему эта логика называется логикой первого порядка. Это значит, что аргументами предикатов могут быть только переменные (кортежи), но не сами предикаты (отношения). Например, в рамках логики первого порядка нельзя сказать: «для любого отношения S верно ...». Тем не менее, как показывает практика, ее выразительной мощности вполне достаточно (интересно, что в самой первой статье Кодд предполагал необходимость использования логики второго порядка).

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

Напомню схему нашей тестовой БД и рассмотрим на ней те же самые примеры, что и для реляционной алгебры (для удобства сравнения я также приведу рядом и выражения алгебры).

Номер поставщика, поставляющего хоть что-нибудь:

s[1]: S(s)                            select distinct vendor#
                                      from   S

S[1]                                  select distinct vendor#
                                      from   S

Имя поставщика, не поставляющего ни одной детали:

v[2]: V(v) ∧ ¬∃s( S(s) ∧ s[1]=v[1] )  select vendor_name
                                      from   V
                                      where  not exists
                                            (select vendor#
                                             from   S
                                             where  S.vendor# = V.vendor#)

(V[1=1](V[1]-S[1]))[2]                select vendor_name
                                      from   V,
                                            (select vendor# from V
                                             minus
                                             select vendor# from S) V2
                                      where  V.vendor# = V2.vendor#

Номер поставщика, поставляющего деталь 15:

s[1]: S(s) ∧ s[2]=15                  select vendor#
                                      from   S
                                      where  S.part# = 15

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

(S[2=1]{15})[1]                       select vendor#
                                      from   S,
                                            (select 15 part# from dual) P
                                      where  S.part# = P.part#

Номер поставщика, поставляющего все детали:

v[1]: V(v) ∧ ∀p( P(p) ∧ ∃s( S(s) ∧    select vendor# 
  ∧ s[2]=p[1] ∧ s[1]=v[1] ) )         from   V 
                                      where  not exists
                                            (select part#
                                             from   P
                                             where  not exists
                                                   (select part#
                                                    from   S
                                                    where  S.part# = P.part# and S.vendor# = V.vendor#) )

В SQL нет аналога квантора всеобщности, но при принятом предположении о замкнутости мира верно ∀x (P) = ¬∃x (¬P).

S[1]-((S[1]⊗P[1])-S)[1]               select vendor# 
                                      from   S 
                                      minus
                                      select vendor#
                                      from  (select S.vendor#, P.part# from S, P
                                             minus
                                             select S.vendor#, S.part# from S)

Справедливости ради обращаю внимание на ловкость рук, с которой написаны SQL-аналоги реляционных выражений. На самом деле надо держать в уме как минимум две особенности SQL: во-первых, таблицы являются не множествами, а мультимножествами; во-вторых, в SQL действует не двузначная логика (истина или ложь, третьего не дано), а трехзначная: истина, ложь и неизвестно (null). Но это отдельная большая (и больная) тема, затрагивать которую здесь не место.

Продолжение следует: 5. Что же выбрать?

Почитать и посмотреть:

К литературе предыдущих разделов добавлю ссылку на статьи по базам данных на сайте Центра Информационных Технологий (спасибо Сергею Дмитриевичу за титанический труд автора и переводчика), а начать рекомендую с:

О пользе классики, полу-классики и не-классики вообще