egorius

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

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

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

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

Более того, Кодд даже придумал на основе исчисления свой реляционный язык Alpha, оказавший сильное влияние на QUEL (query language) — язык одной из первых реляционных СУБД Ingres, разработанной в Беркли. QUEL строго следовал реляционной модели; рискну предположить, что это внесло свой вклад в то, что в итоге победил SQL. SQL изначально был основан на алгебре, но с самого начала отступил от стройной теории (вспомним про мультимножества и трехзначную логику), за что до сих пор порицаем ортодоксами. Тем не менее он оказался более практичным (наверное, и более везучим), чем его академический собрат.

Это, конечно, не означает, что алгебра таки «лучше» исчисления. SQL и сам изрядно обогатился ее арсеналом, а кроме того, существуют и другие языки, построенные на фундаменте матлогики и реляционного исчисления. Самым известным из них является Пролог. Он появился во Франции в начале 1970-х — как раз в то время, о котором мы ведем речь, — но совершенно вне контекста баз данных, а именно в связи с исследованиями по обработке естественных языков.

Пик популярности Пролога пришелся на 1980-е, время увлечения искусственным интеллектом и экспертными системами. Сейчас интерес к этому языку спал, но Пролог жив и на его основе создаются новые интересные языки (в частности, для параллельных вычислений).

Возможно, любители Пролога осознают его родство с SQL, но большинство программирующих на SQL, боюсь, про Пролог даже не в курсе. Поэтому позволю себе мимоходом показать сходство этих двух языков на все том же примере с поставщиками и деталями.

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

  supply_something(X) :-                select distinct vendor#
     supply(X,_).                       from   S
  

  supply_something(X) верно, если поставщик X поставляет деталь с неважно каким именем.

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

  supply_nothing(VN) :-                 select vendor_name
    vendor(V,VN), \+(supply(V,_)).      from   V
                                        where  not exists
                                              (select vendor#
                                               from   S
                                               where  S.vendor# = V.vendor#)
  

  supply_nothing(VN) верно, если существует поставщик V с именем VN, и не верно, что поставщик V поставляет произвольную деталь.

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

  supply_15(X) :-                       select vendor#
    supply(X,15).                       from   S
                                        where  S.part# = 15
  

  supply_15(X) верно, если поставщик X поставляет деталь 15.

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

  missing(V,P) :-                       select vendor# 
    vendor(V,_), part(P),               from   V 
    \+(supply(V,P)).                    where  not exists
  supply_all(V) :-                            (select part#
    vendor(V,_), \+(missing(V,P)).             from   P
                                               where  not exists
                                                     (select part#
                                                      from   S
                                                      where  S.part# = P.part# and S.vendor# = V.vendor#) )
  

  Разобьем на две части. missing(V,P) верно, если существует поставщик V с любым именем, существует деталь P, и не верно, что V поставляет P. Говоря неформально, missing(V,P) означает «поставщик V не поставляет P».

  supply_all(V) верно, если существует поставщик V с любым именем, и не верно, что для любой детали P «поставщик V не поставляет P».

Как видим, Пролог справляется с примерами из мира СУБД. Поглядим еще на классическую рекурсивную задачу из мира Пролога. Пусть имеются факты о том, кто кому приходится родителем. Нужно определить, кто кому приходится предком (родителем, прародителем и т. п.).

Сначала определим несколько фактов о непосредственных родителях:

parent('Abraham','Isaac').
parent('Isaac','Jacob').
parent('Jacob','Judas').

Теперь можно определить понятие предка:

ancestor(B,A) :- parent(B,A).
ancestor(Z,A) :- parent(B,A), ancestor(Z,B).

Это либо непосредственный родитель (первое правило), либо существует какой-то непосредственный родитель, в свою очередь являющийся предком (второе правило).

Теперь Прологу можно задать вопрос: покажи все возможные пары людей и их предков.

| ?- ancestor(X,Y).

X = 'Abraham'
Y = 'Isaac' ? ;

X = 'Isaac'
Y = 'Jacob' ? ;

X = 'Jacob'
Y = 'Judas' ? ;

X = 'Abraham'
Y = 'Jacob' ? ;

X = 'Isaac'
Y = 'Judas' ? ;

X = 'Abraham'
Y = 'Judas' ? ;

no

Пролог перечислит по очереди все найденные пары и остановится с сообщением no (больше нет).

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

with people(parent_name,name) as (         -- факты о родителях
        select 'Abraham', 'Isaac' from dual
        union
        select 'Isaac',   'Jacob' from dual
        union
        select 'Jacob',   'Judas' from dual
     ),
     ancestor(ancestor_name,name) as (     -- предок - это...
        select p.parent_name,              -- ...непосредственный родитель...
               p.name
        from   people p
        union all
        select a.ancestor_name,            -- ...или предок родителя
               p.name
        from   people p,
               ancestor a
        where  p.parent_name = a.name
     )
select *
from   ancestor;
 
ANCESTOR NAME
-------- -----
Abraham  Isaac
Isaac    Jacob
Jacob    Judas
Abraham  Jacob
Isaac    Judas
Abraham  Judas
 
6 rows selected

В Оракле такой синтаксис работает, начиная с версии 11.2.

Безусловно, между Прологом и SQL масса различий: и в синтаксисе, и в сфере применения. Но общий математический фундамент тем не менее налицо.

Продолжение следует: 6. System R, Phase Zero

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