Реляционное исчисление кортежей - Tuple relational calculus

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

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

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

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

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

ч : R → 2 ^С

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

т : C ⇸ D

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

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

дБ : R → 2 ^{T _D}

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

dom ( t ) = h ( r ).

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

Атомы

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

если v и w в V , a в типе ( v ) и b в типе ( w ), то формула v . а = ш . b находится в A [ S , type ],
если v в V , a в типе ( v ) и k обозначает значение в D, то формула v . a = k принадлежит A [ S , type ], и
если v в V , r в R и type ( 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 → T _D, которая сопоставляет переменные кортежа с кортежами по области в S :

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

Формулы

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

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

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

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

Обратите внимание, что последняя формула утверждает, что все книги, написанные CJ Date, имеют в качестве предмета реляционную модель. Как обычно, мы опускаем скобки, если это не вызывает двусмысленности в семантике формулы.

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

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 : H | f ( v )}

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

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

{ t : {name} | ∃ s : {имя, заработная плата} (Сотрудник ( ы ) ∧ s. Заработная плата = 50 000 ∧ t .name = s. Name)}
{ t : {поставщик, статья} | ∃ s : {s #, sname} (Поставщик ( и ) ∧ 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 = {("г ₁ ", {("а", 1)})}

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

{ t : {a} | t .a = t .a}

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

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

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

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

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

в " 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, если он выполняется либо в f _1, либо в f ₂ ,
в « f ₁ ∨ f ₂ » выполняется v . а == ш . b, если он выполняется как в f _{1, так} и в 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 ∨ ∃ w (r (w) ∧ ( v .b = w .a ∨ v .b = w .b))

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

Languages

In other projects

Реляционное исчисление кортежей - Tuple relational calculus

СОДЕРЖАНИЕ