Кортежное реляционное исчисление

Исчисление кортежей — это исчисление , которое было создано и представлено Эдгаром Ф. Коддом как часть реляционной модели , чтобы предоставить декларативный язык запросов к базе данных для манипулирования данными в этой модели данных . Он послужил источником вдохновения для языков запросов к базе данных QUEL и SQL , из которых последний, хотя и гораздо менее верный исходной реляционной модели и исчислению, теперь является де-факто стандартным языком запросов к базе данных; диалект SQL используется почти в каждой системе управления реляционными базами данных . Мишель Лакруа и Ален Пиротт предложили исчисление предметной области , которое ближе к логике первого порядка , и вместе с Коддом показали, что оба этих исчисления (а также реляционная алгебра ) эквивалентны по выразительной силе. Впоследствии языки запросов для реляционной модели стали называться реляционно полными , если они могли выразить хотя бы все эти запросы.

Определение исчисления

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

Поскольку исчисление является языком запросов для реляционных баз данных, нам сначала необходимо определить реляционную базу данных. Базовым строительным блоком реляционных данных является домен (несколько похожий, но не равный типу данных ). Кортеж — это конечная последовательность атрибутов , которые представляют собой упорядоченные пары доменов и значений. Отношение — это набор (совместимых) кортежей. Хотя эти реляционные концепции определены математически, эти определения во многом соответствуют традиционным концепциям баз данных. Таблица ; — это общепринятое визуальное представление отношения кортеж аналогичен понятию строки .

Сначала мы предполагаем существование набора C имен столбцов, примерами которых являются «имя», «автор», «адрес» и т. д. Мы определяем заголовки как конечные подмножества C . Схема реляционной базы данных определяется как кортеж S = ( D , R , h ), где D — область атомарных значений ( см. в реляционной модели подробнее о понятиях области и атомарного значения ), R — конечный набор имен отношений. , и

ч : Р → 2 ^С

функция , которая связывает заголовок с каждым именем отношения R. в (Обратите внимание, что это упрощение полной реляционной модели, в которой существует более одного домена, а заголовок представляет собой не просто набор имен столбцов, но также сопоставляет имена этих столбцов с доменом.) Учитывая домен D , мы определяем кортеж для D как частичная функция которая сопоставляет имена некоторых столбцов с атомарными значениями в D. , Примером может быть (имя: «Гарри», возраст: 25).

т : С ⇸ D

Множество всех кортежей над D обозначается TD _как . Подмножество C, для которого определен кортеж t, называется доменом t dom (не путать с доменом в схеме) и обозначается как ( t ) .

Наконец, мы определяем реляционную базу данных по схеме S = ( D , R , h ) как функцию

дБ : Р → 2 ^{Т _Д}

который отображает имена отношений в , так что _{R в конечные подмножества TD} для каждого имени отношения r в R и кортежа t в db ( r ) выполняется соотношение

дом ( т ) знак равно час ( р ).

Последнее требование просто гласит, что все кортежи в отношении должны содержать одинаковые имена столбцов, а именно те, которые определены для него в схеме.

Атомы

Для построения формул будем предполагать бесконечное множество V кортежа переменных. Формулы определены с учетом схемы базы данных S = ( D , R , h частичной функции ) и типа : V ⇸ 2 ^С, вызываемый при назначении типа , который присваивает заголовки некоторым переменным кортежа. Затем мы определяем набор атомарных формул A [ S , type ] по следующим правилам:

если v и w в V , a в типе ( v ) и b в типе ( w ), то формула v . а = ш . b находится в A [ S , тип ],
если v в V , a в типе ( v ) и k обозначает значение в D , то формула v . a = k находится в A [ S , type ], и
если v в V , r в R и тип ( v ) = h ( r ), то формула r ( v ) находится в A [ S , type ].

Примеры атомов:

( t .age = s .age) — t имеет атрибут возраста, а s имеет атрибут возраста с тем же значением.
( t .name = "Codd") — кортеж t имеет атрибут name и его значение — "Codd"
Book( t ) — кортеж t присутствует в отношении Book.

Формальная семантика таких атомов определяется с учетом базы данных db над S и привязки переменной кортежа val : V → TD _, которая отображает переменные кортежа в кортежи в области S :

в . а = ш . b истинно тогда и только тогда, когда val ( v )( a ) = val ( w )( b )
в . a = k истинно тогда и только тогда, когда val ( v )( a ) = k
r ( v ) истинно тогда и только тогда, когда val ( v ) находится в db ( r )

Формулы

Атомы можно объединять в формулы, как это обычно бывает в логике первого порядка, с помощью логических операторов ∧ (и), ∨ (или) и ¬ (не), а также мы можем использовать квантор существования (∃) и квантор всеобщности. (∀) для привязки переменных. Мы определяем множество формул F [ S , type ] индуктивно по следующим правилам:

каждый атом в A [ S , тип ] также находится в F [ S , тип ]
если f ₁ и f ₂ находятся в F [ S , тип ], то формула f ₁ ∧ f ₂ также находится в F [ S , тип ]
если f ₁ и f ₂ находятся в F [ S , тип ], то формула f ₁ ∨ f ₂ также находится в F [ S , тип ]
если f находится в F [ S , тип ], то формула ¬ f также находится в F [ S , тип ]
если v в V , H заголовок и f формула в F [ S , тип _{[ v -> H ]} ], то формула ∃ v : H ( f ) также находится в F [ S , тип ], где тип _{[ v - > H ]} обозначает функцию, которая равна типу, за исключением того, что она отображает v в H ,
если v в V , H заголовок и f формула в F [ S , тип _{[ v -> H ]} ], то формула ∀ v : H ( f ) также находится в F [ S , тип ]

Примеры формул:

t .name = "CJ Date" ∨ t .name = "Х. Дарвен"
Книга( т ) ∨ Журнал( т )
∀ t : {автор, название, тема} ( ¬ ( Book( t ) ∧ t .author = "CJ Date" ∧ ¬ ( t .subject = "реляционная модель")))

Обратите внимание: последняя формула утверждает, что все книги, написанные Си Джей Дейтом, посвящены реляционной модели. Как обычно, мы опускаем скобки, если это не вызывает двусмысленности в семантике формулы.

Мы будем предполагать, что кванторы количественно оценивают совокупность всех кортежей в домене схемы. Это приводит к следующей формальной семантике для формул с базой данных db над S привязкой переменной кортежа val : V -> TD _и :

f ₁ ∧ f ₂ истинно тогда и только тогда, когда f ₁ истинно и f ₂ истинно,
f ₁ ∨ f ₂ истинно тогда и только тогда, когда f ₁ истинно, или f ₂ истинно, или оба верны,
¬ f истинно тогда и только тогда, когда f неверно,
∃ v : H ( f ) истинно тогда и только тогда, когда существует кортеж t над D такой, что dom ( t ) = H и формула f верна для val _{[ v -> t ]} и
∀ v : H ( f ) истинно тогда и только тогда, когда для всех кортежей t над D таких, что dom ( t ) = H , формула f верна для val _{[ v -> t ]} .

Запросы

Наконец, мы определяем, как выглядит выражение запроса с учетом схемы S = ( D , R , h ):

{ v : Ч | ж ( v ) }

где v — переменная-кортеж, H — заголовок, а f ( v ) — формула в F [ S , type ], где type = {( v , H ) } и с v в качестве единственной свободной переменной. Результатом такого запроса для данной базы данных db над S является набор всех кортежей t над D с dom ( t ) = H таких, что f истинно для db и val = { ( v , t ) }.

Примеры выражений запроса:

{ т : {имя} | ∃ s : {имя, заработная плата} (Сотрудник( s ) ∧ s .wage = 50.000 ∧ t .name = s .name ) }
{ т : {поставщик, артикул} | ∃ s : {s#, pname} ( Поставщик( s ) ∧ s .sname = t .supplier ∧ ∃ p : {p#, pname} ( Product( p ) ∧ p .pname = t .article ∧ ∃ a : { s#, p#} ( Supplies( a ) ∧ s .s# = a .s# ∧ a .p# = p .p# ))) }

Семантическое и синтаксическое ограничение исчисления

Независимые от домена запросы

Поскольку семантика кванторов такова, что они оценивают все кортежи в домене схемы, запрос может вернуть другой результат для определенной базы данных, если предполагается другая схема. Например, рассмотрим две схемы S ₁ = ( D ₁ , R , h ) и S ₂ = ( D ₂ , R , h ) с доменами D ₁ = { 1 }, D ₂ = { 1, 2 }, именами отношений R = { "r ₁ " } и заголовки h = { ("r ₁ ", {"a"}) }. Обе схемы имеют общий экземпляр:

db = { ( "r ₁ ", { ("a", 1) } ) }

Если мы рассмотрим следующее выражение запроса

{ т : {а} | т .а = т .а }

тогда его результатом на db будет либо { (a : 1) } при S ₁ , либо { (a : 1), (a : 2) } при S ₂ . Также будет ясно, что если мы возьмем область определения как бесконечное множество, то результат запроса также будет бесконечным. Чтобы решить эти проблемы, мы ограничим наше внимание теми запросами, которые не зависят от предметной области , т. е. запросами, которые возвращают один и тот же результат для базы данных во всех ее схемах.

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

Безопасные запросы

Чтобы ограничить выражения запроса так, чтобы они выражали только запросы, независимые от предметной области, синтаксическое понятие безопасного запроса обычно вводится . Чтобы определить, является ли выражение запроса безопасным, мы получим два типа информации из запроса. Во-первых, существует ли пара переменная-столбец t . a привязан к столбцу отношения или константы, а второй — приравниваются ли две пары переменная-столбец прямо или косвенно (обозначается t . v == s . w ).

Для вывода ограниченности введем следующие правила рассуждений:

в " v . a = w . b " никакая пара переменная-столбец не связана,
в " v . a = k " пара переменных-столбцов v . а связан,
в " r ( v )" все пары v . a связаны для a в типе ( v ),
в " f ₁ ∧ f ₂ " связаны все пары, которые связаны либо в f _1, либо в f ₂ ,
в " f ₁ ∨ f ₂ " связаны все пары, которые связаны как в f _1, так и в f ₂ ,
в " ¬f " пары не связаны,
в " ∃ v : H ( f ) " пара w . a связан, если он связан в f и w <> v , и
в " ∀ v : H ( f ) " пара w . a связан, если он связан в f и w <> v .

Для вывода эквивалентности введем следующие правила рассуждений (кроме обычных правил рассуждения для отношений эквивалентности: рефлексивности, симметрии и транзитивности):

" v.a , " = w.b в что верно v . а == ш . б ,
в " = v.a никакие k " пары не приравниваются,
в « r ( v )» пары не приравниваются,
в " f ₁ ∧ f ₂ " верно, что v . а == ш . b, оно выполняется либо в f1 _, либо в f2 _если ,
в " f ₁ ∨ f ₂ " верно, что v . а == ш . b, если оно справедливо как в f ₁ , так и в f ₂ ,
в " ¬f " никакие пары не отождествляются,
в "∃ v : H ( f )" справедливо w . а == х . b, если оно выполняется в f и w <> v и x <> v и
в "∀ v : H ( f )" справедливо w . а == х . b, если оно выполняется в f и w <> v и x <> v .

Затем мы говорим, что выражение запроса { v : H | f(v) } безопасно , если

для каждого имени столбца a в H мы можем вывести это v . a приравнивается к связанной паре в f ,
для каждого подвыражения f формы «∀ w : G ( g )» мы можем вывести, что для каждого имени столбца a в G мы можем вывести это w . a приравнивается к связанной паре в g и
для каждого подвыражения f формы «∃ w : G ( g )» мы можем вывести, что для каждого имени столбца a в G мы можем вывести это w . a приравнивается к связанной паре в g .

Ограничение на безопасные выражения запроса не ограничивает выразительность, поскольку все доменно-независимые запросы, которые могут быть выражены, также могут быть выражены с помощью безопасного выражения запроса. Это можно доказать, показав, что для схемы S = ( D , R , h ), заданного набора K констант в выражении запроса, переменной кортежа v и заголовка H мы можем построить безопасную формулу для каждой пары v . a с a в H , что означает, что его значение находится в активной области. Например, предположим, что K = {1,2}, R = {"r"} и h = { ("r", {"a, "b"}) }, тогда соответствующая безопасная формула для v .b:

v .b знак равно 1 ∨ v .b знак равно 2 ∨ ∃ ш ( р(ш) ∧ ( v .b знак равно ш .а ∨ v .b знак равно ш .b ) )

Эту формулу затем можно использовать для перезаписи любого небезопасного выражения запроса в эквивалентное безопасное выражение запроса, добавляя такую формулу для каждой переменной v и имени столбца a в ее типе, где она используется в выражении. Фактически это означает, что мы позволяем всем переменным варьироваться по активному домену, что, как уже объяснялось, не меняет семантику, если выраженный запрос не зависит от домена.

Системы

См. также

Ссылки

Эдгар Ф. Кодд : Реляционная модель данных для больших общих банков данных . Сообщения ACM , 13(6):377–387, 1970.