![[personal profile]](https://www.dreamwidth.org/img/silk/identity/user.png){kind=small}
История SQL. 4. Реляционное исчисление
Jan. 9th, 2012 01:18 amНачало: 1. Необходимая предыстория, назад: 3. Реляционная алгебра.
Если реляционная алгебра более или менее привычна (что не удивительно, поскольку SQL в основном базируется именно на ней), то с исчислением дело обстоит хуже. Реляционное исчисление основано не на теории множеств, а на другом формализме — логике предикатов первого порядка. Впервые Кодд подробно описал его в работе 1972 года, хотя и упоминал с самой первой статьи.
Логика предикатов корнями уходит в труды Аристотеля (а это IV век до н. э), который пытался свести рассуждения об истинности любого предположения к формальным правилам вывода новых фактов из имеющихся (силлогизмы Аристотеля).
В нынешнем понимании, логика предикатов имеет дело со следующими объектами. Во-первых, с константами и переменными. Во-вторых, с предикатами, под которыми понимаются булевские (т. е. принимающие истинное или ложное значение) функции, аргументами которых могут выступать константы и переменные. В-третьих, предикаты объединяются в выражения с помощью логических связок: и (∧), или (∨), не (¬).
Предикаты связаны с отношениями вот как. Возьмем какое-нибудь отношение, допустим, V. Неформальный смысл этого отношения можно определить так: «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 SS[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. Что же выбрать?
