egorius | История SQL. 3. Реляционная алгебра

Начало: 1. Необходимая предыстория, назад: 2. Программист-навигатор.

Итак, к концу 1960-х рынок СУБД (а рынок как таковой только начал формироваться: до этого продавали аппаратуру, а не программы) был представлен сетевой системой IDS Бахмана (General Electric), иерархической IMS (IBM) и некоторыми другими, менее известными. Несмотря на то, что сейчас мы говорим «сетевая модель» и «иерархическая модель», эти продукты разрабатывались без какой-либо четкой математической концепции; во главу угла была поставлена эффективность кода.

Примерно в этот момент (1968 год) базами данных заинтересовался Эдгар Кодд, работавший в IBM. Его идея была в том, что привлечь новых заказчиков можно только простым и понятным способом извлечения информации из баз данных, а такой способ должен опираться на стройную модель. Будучи математиком, он заметил связь между хранимыми в БД данными и логическими высказываниями. Через год работы появился внутренний отчет IBM, а в начале 1970 — знаменитая статья в Communications of ACM.

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

Центральным понятием реляционной теории является отношение (relation) — то, что обычно мы называем таблицей (иногда ошибочно полагают, что под отношением имеется в виду связь между двумя таблицами, путая, возможно, с entity-relationship diagram). Отношение является множеством кортежей (tuple), состоящих из атрибутов (attribute). Для каждого атрибута определен тип данных; количество атрибутов определяет степень (или арность) отношения. В обычной терминологии кортеж отношения — это строка таблицы, а атрибут — столбец.

Однако несмотря на внешнее сходство отношений и таблиц, надо понимать, что отношения, будучи множествами, обладают важными свойствами, не всегда верными для таблиц SQL:

В отношении нет повторяющихся кортежей (а в SQL мы, как правило, работаем с мультимножествами и при необходимости должны устранять дубликаты явно, например, с помощью DISTINCT). Как следствие, в отношении всегда существует первичный ключ (в SQL это необязательно).
Кортежи не упорядочены (следовательно, конструкция ORDER BY немедленно выводит нас за рамки реляционной теории).

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

Кодд предложил два способа работы с отношениями. Первый — реляционная алгебра — использует тот факт, что отношения являются множествами (хоть и специального вида), а, значит, к ним применимы такие традиционные теоретико-множественные операции, как объединение (∪), пересечение (∩) и разность (−). Единственная тонкость в том, что для этих операций отношения должны иметь одинаковый набор атрибутов — иначе результат будет множеством, но перестанет быть отношением.

На SQL эти операции обозначаются UNION (но не UNION ALL!), INTERSECT и MINUS.

Кроме того, Кодд ввел несколько дополнительных операций над отношениями. Тут я буду придерживаться нотации, которую Кодд использует в статье 1972 года. Также вслед за ним я буду обозначать атрибуты номерами, хотя Кодд и сам говорил, что в реальных системах имена будут удобнее. С тех пор теория сильно шагнула вперед, и в работах Дейта нотация уже совсем иная.

Проекция оставляет из всего набора атрибутов некоторое их подмножество. Например, проекция отношения A на 2 и 5 атрибуты обозначается A[2,5].

В SQL эта операция обеспечиваются фразой SELECT DISTINCT (т. к. в отношении, в том числе результирующем, не может быть дубликатов).

Соединение двух отношений по условию равенства общих атрибутов порождает новое отношение, кортежи которого являются конкатенациями всевозможных пар кортежей исходных отношений, для которых выполняется это условие. Например, если у отношений A и B общими считаются атрибуты A[1] и B[3], то соединение обозначается A[1=3]B.

Такое соединение называют еще эквисоединением. Частный его случай, когда два отношения не имеют общих атрибутов, называется расширенным декартовым произведением: A⊗B.

В SQL соединения формулируются во фразе FROM. Особенно отчетливо это видно в ANSI-синтаксисе, где условия соединения выписываются явно, а в традиционном синтаксисе условия переходят во фразу WHERE.

Ограничение оставляет лишь те кортежи, которые удовлетворяют определенному условию на атрибуты. Например, ограничение отношения A по условию, что атрибут 1 больше, чем атрибут 2: A[1 > 2].

Ограничения в SQL записываются во фразе WHERE.

Введенные операции и формируют реляционную алгебру. Поскольку каждая операция выполняется над отношениями и результатом каждой операции также являются отношения, то операции можно комбинировать в выражения. Это полезное свойство называют замкнутостью алгебры.

Рассмотрим несколько запросов на следующем, почти классическом, примере: имеются поставщики (V — VENDORS) и детали (P — PARTS), связаные многие-ко-многим поставками (S — SUPPLIES).

Рядом с выражением реляционной алгебры для пущей ясности приводится непосредственный аналог на SQL.

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

S[1]                            select distinct vendor#
                                from   S

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

(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[2=1]{15})[1]                 select vendor#
                                from   S,
                                      (select 15 part# from dual) P
                                where  S.part# = P.part#
```
Выражение в фигурных скобках представляет собой литерал отношения, отсутствующий в SQL — его пришлось имитировать выборкой из dual.

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

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)

Такую операцию Кодд даже рассмотрел отдельно, введя для нее имя реляционного деления.

В заключение дам слово Дону Чемберлину. «Тед (друзья Эдгара Кодда называли его Тедом) организовал симпозиум в исследовательском отделе IBM. Это было мое первое знакомство с мощью математического подхода к управлению базами данных. Я довольно плотно изучал интерфейс CODACYL и мог представить себе, как будет выглядеть запрос, когда надо получить что-то из базы данных... Пришел Тед и начал придумывать из головы запросы и писать их на доске на своем реляционном языке. И они получались очень короткие и понятные. ... С той поры мне уже не хотелось больше работать с CODASYL, потому что я увидел потенциал реляционного подхода».

Продолжение следует: 4. Реляционное исчисление.

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

Крис Дейт, «Введение в системы баз данных», «SQL и реляционная теория»
Сергей Кузнецов, «Основы современных баз данных»
Oral History of Donal Chamberlin в Computer History Museum.

История SQL. 3. Реляционная алгебра

no subject

no subject