Исчисление кортежей — это исчисление, созданное и представленное Эдгаром Ф. Коддом как часть реляционной модели , чтобы предоставить декларативный язык запросов к базе данных для манипулирования данными в этой модели данных . Оно послужило источником вдохновения для языков запросов к базе данных QUEL и SQL , из которых последний, хотя и гораздо менее верен исходной реляционной модели и исчислению, в настоящее время является фактическим стандартным языком запросов к базе данных; диалект SQL используется почти каждой реляционной системой управления базами данных . Мишель Лакруа и Ален Пиротт предложили исчисление доменов , которое ближе к логике первого порядка , и вместе с Коддом показали, что оба этих исчисления (а также реляционная алгебра ) эквивалентны по выразительной мощности. Впоследствии языки запросов для реляционной модели были названы реляционно полными , если они могли выразить по крайней мере все эти запросы.
Поскольку исчисление является языком запросов для реляционных баз данных, мы сначала должны определить реляционную базу данных. Основным реляционным строительным блоком является домен ( несколько похожий, но не равный, типу данных ). Кортеж — это конечная последовательность атрибутов , которые являются упорядоченными парами доменов и значений. Отношение — это набор (совместимых) кортежей. Хотя эти реляционные концепции определены математически, эти определения свободно сопоставляются с традиционными концепциями баз данных. Таблица — это принятое визуальное представление отношения; кортеж похож на концепцию строки .
Сначала мы предполагаем существование набора C имен столбцов, примерами которых являются «имя», «автор», «адрес» и т. д. Мы определяем заголовки как конечные подмножества C. Схема реляционной базы данных определяется как кортеж S = ( D , R , h ), где D — домен атомарных значений (см. реляционную модель для получения дополнительной информации о понятиях домена и атомарного значения ), R — конечный набор имен отношений, а
функция , которая связывает заголовок с каждым именем отношения в R. (Обратите внимание, что это упрощение полной реляционной модели, где есть более одного домена, и заголовок — это не просто набор имен столбцов, но и отображение этих имен столбцов в домен.) Для заданного домена D мы определяем кортеж над D как частичную функцию , которая отображает некоторые имена столбцов в атомарное значение в D. Примером может быть (имя: "Гарри", возраст: 25).
Множество всех кортежей над D обозначается как T D. Подмножество C, для которого определен кортеж t, называется доменом t ( не путать с доменом в схеме) и обозначается как dom ( t ).
Наконец, мы определяем реляционную базу данных , заданную схемой S = ( D , R , h ) как функцией
который отображает имена отношений в R в конечные подмножества T D , так что для каждого имени отношения r в R и кортежа t в db ( r ) выполняется следующее:
Последнее требование просто говорит о том, что все кортежи в отношении должны содержать одинаковые имена столбцов, а именно те, которые определены для него в схеме.
Для построения формул мы предположим бесконечное множество V переменных кортежа. Формулы определяются с учетом схемы базы данных S = ( D , R , h ) и частичной функции type : V ⇸ 2 C , вызываемой при назначении типа , которая назначает заголовки некоторым переменным кортежа. Затем мы определяем множество атомарных формул A [ S , type ] со следующими правилами:
Примерами атомов являются:
Формальная семантика таких атомов определяется с учетом базы данных db над S и связывания переменных кортежа val : V → T D , которая сопоставляет переменные кортежа с кортежами над доменом в S :
Атомы могут быть объединены в формулы, как это обычно бывает в логике первого порядка, с помощью логических операторов ∧ (и), ∨ (или) и ¬ (не), и мы можем использовать квантификатор существования (∃) и квантификатор всеобщности (∀) для связывания переменных. Мы определяем множество формул F [ S , тип ] индуктивно с помощью следующих правил:
Примеры формул:
Обратите внимание, что последняя формула утверждает, что все книги, написанные CJ Date, имеют в качестве своего предмета реляционную модель. Как обычно, мы опускаем скобки, если это не вызывает двусмысленности относительно семантики формулы.
Мы предположим, что квантификаторы квантифицируют по вселенной всех кортежей по домену в схеме. Это приводит к следующей формальной семантике для формул, заданных базой данных db по S и связыванием переменной кортежа val : V -> T D :
Наконец, мы определяем, как выглядит выражение запроса, учитывая схему S = ( D , R , h ):
где v — переменная кортежа, H — заголовок, а f ( v ) — формула в F [ S , type ], где type = { ( v , H ) } и v — единственная свободная переменная. Результатом такого запроса для заданной базы данных db над S является набор всех кортежей t над D с dom ( t ) = H , таких что f истинно для db и val = { ( v , t ) }.
Примеры выражений запроса:
Поскольку семантика квантификаторов такова, что они квантифицируют все кортежи по домену в схеме, может случиться так, что запрос может вернуть другой результат для определенной базы данных, если предполагается другая схема. Например, рассмотрим две схемы S 1 = ( D 1 , R , h ) и S 2 = ( D 2 , R , h ) с доменами D 1 = { 1 }, D 2 = { 1, 2 }, именами отношений R = { "r 1 " } и заголовками h = { ("r 1 ", {"a"}) }. Обе схемы имеют общий экземпляр:
Если мы рассмотрим следующее выражение запроса
то его результат в db будет либо { (a : 1) } при S 1 , либо { (a : 1), (a : 2) } при S 2 . Также будет ясно, что если мы возьмем домен как бесконечное множество, то результат запроса также будет бесконечным. Чтобы решить эти проблемы, мы ограничим наше внимание теми запросами, которые независимы от домена , т. е. запросами, которые возвращают один и тот же результат для базы данных при всех ее схемах.
Интересным свойством этих запросов является то, что если мы предположим, что переменные кортежа ранжируются по кортежам в так называемом активном домене базы данных, который является подмножеством домена, которое встречается по крайней мере в одном кортеже в базе данных или в выражении запроса, то семантика выражений запроса не меняется. Фактически, во многих определениях исчисления кортежей именно так определяется семантика квантификаторов, что делает все запросы по определению независимыми от домена.
Чтобы ограничить выражения запроса таким образом, чтобы они выражали только запросы, независимые от домена, обычно вводится синтаксическое понятие безопасного запроса . Чтобы определить, является ли выражение запроса безопасным, мы выведем два типа информации из запроса. Первый — связана ли пара переменная-столбец t . a со столбцом отношения или константой, а второй — приравнены ли две пары переменная-столбец напрямую или косвенно (обозначается t . v == s . w ).
Для вывода ограниченности введем следующие правила рассуждений:
Для вывода эквивалентности введем следующие правила рассуждения (наряду с обычными правилами рассуждения для отношений эквивалентности: рефлексивность, симметрия и транзитивность):
Затем мы говорим, что выражение запроса { v : H | f(v) } является безопасным , если
Ограничение на безопасные выражения запросов не ограничивает выразительность, поскольку все доменно-независимые запросы, которые могут быть выражены, также могут быть выражены безопасным выражением запроса. Это можно доказать, показав, что для схемы S = ( D , R , h ), заданного набора констант K в выражении запроса, переменной кортежа v и заголовка H мы можем построить безопасную формулу для каждой пары v . a с a в H , которая утверждает, что ее значение находится в активном домене. Например, предположим, что K = {1,2}, R = {"r"} и h = { ("r", {"a, "b"}) }, тогда соответствующая безопасная формула для v .b будет:
Эта формула, таким образом, может быть использована для переписывания любого небезопасного выражения запроса в эквивалентное безопасное выражение запроса путем добавления такой формулы для каждой переменной v и имени столбца a в его типе, где она используется в выражении. Фактически это означает, что мы позволяем всем переменным находиться в диапазоне активного домена, что, как уже объяснялось, не меняет семантики, если выраженный запрос не зависит от домена.