Реляционное вычисление доменов.
Реляционное вычисление кортежей.
Элементы реляционного исчисления.
В отличие от реляционной алгебры (процедурный подход), реляционное исчисление реализует декларативный (описательный) подход к выполнению операций над данными, поскольку оно лишь описывает свойства желаемого результата в виде логической формулы.
Основная идея состоит в том, чтобы любую операцию над отношениями описать в виде правильной формулы. СУБД, основанные на реляционном исчислении, автоматически распознают эти формулы и выполняют требуемые преобразования над данными. Достоинством такого подхода является то, что он позволяет построить непроцедурные языки манипулирования данными.
Базисными понятиями реляционного исчисления являются:
- понятие переменной с определенной для нее областью допустимых значений.
- понятие правильно построенной формулы, опирающейся на переменные, предикаты и кванторы.
Аналитические выражения записывают в одной из следующих форм:
а) { t | Y (t) } - читается так: “множество переменных t таких, что истинна формула Y “
б) { t1, t2,... tk | Y ‘ (t1, t2,... tk) }
где t - переменная - кортеж,
t1,...tk - переменные на доменах,
k - ранг отношения,
Y - формула, построенная из атомов.
В зависимости от того, что является областью определения переменной, различают исчисление кортежей и исчисление доменов. В первом случае (а)) в качестве значений переменных используются кортежи, во втором (б)) - домены.
8.2. Реляционное исчисление кортежей
Атомы формул Y могут быть трех типов:
1. R(S) - означает, что S - это кортеж в отношении R
2. s[i] @ u[j] - означает, что i-ая компонента S и j -ая компонента U связаны оператором сравнения (< > =). Например: s[1] < u[3] справедливо для кортежей s = (1, 6, 6, 6) и u = (2, 2, 5, 2)
3. s[i] @ const или const @ s[i], - аналогичная п.2 связь с константой. Например, s[3] = “СИДОРОВ”
Формулы составляются из атомов по следующим правилам:
1. Каждый атом - это формула
2. Если Y 1 и Y 2 - формулы, то Y 1 Щ Y 2, Y 1 Ъ Y 2, Ш Y 1 - тоже формулы.
3. Если Y - формула, то ($ s) (Y) - тоже формула, которая утверждает, что существует такое значение переменной S, при котором Y истинна.
4. Если Y - формула, то (" s) (Y) - тоже формула, которая утверждает, что при подстановке любого значения переменной S в формулу Y она остается истинной.
5. Порядок старшинства операций в формулах: операторы сравнения (< > = и т.п.), $, ", Ш,Щ,Ъ
Правильно построенные формулы служат для описания условий, которые накладываются пользователем на кортежные переменные. В условиях применяются только простые сравнения атрибутов отношений с константой или с другим атрибутом.
При использовании кортежных переменных можно ссылаться на отдельный атрибут этой переменной, например: если S = (5, Иванов, 500, 3) - это кортеж отношения СОТРУДНИКИ (номер, имя, оклад, отдел), то S [3] = 500 - это значение третьего атрибута данного кортежа (оклад). На практике в языках, основанных на реляционном исчислении, часто вместо номера атрибута используют его имя, например, вместо S [3] пишут S.Оклад, что более наглядно.
Переменные, входящие в формулы, могут быть свободными или связанными. К свободным относят все переменные, входящие в формулу, при построении которой не использовались кванторы. Множество кортежей - значений этих переменных, при которых формула истинна, образуют результирующее отношение.
Если же имя переменной Х использовано сразу после квантора $ Х или " Х, то она считается связанной переменной, которая не видна за пределами формулы, описанной в кванторе. При вычислении значения такой формулы используется не одно значение связанной переменной, а вся ее область определения. Например, пусть Х и Y - две кортежные переменные, определенные на отношении СОТРУДНИКИ. Тогда, формула
$ Y (Х.Оклад > Y.Оклад)
для текущего значения Х истинна в том и только в том случае, если во всем отношении СОТРУДНИКИ найдется кортеж Y такой, что значение его атрибута Оклад удовлетворяет заданному условию сравнения.
Чтобы описать, какие атрибуты кортежа должны входить в результирующее отношение, используют целевой список, который может состоять из следующих элементов:
1. Х.А где Х - имя свободной переменной, а А - имя атрибута отношения
2. Х, то есть имена всех атрибутов отношения
3. N = X.A, где N - новое имя атрибута результирующего отношения (когда используются несколько переменных с одинаковой областью определения)
В реальных языках БД вместо математических обозначений кванторов и логических связок используют, как правило, словесные обозначения:
$ | EXISTS | Ш | NOT |
" | FORALL | Щ | AND |
| | WHERE | Ъ | OR |
Таким образом, аналитическое выражение реляционного исчисления кортежей можно записать в виде:
ЦелевойСписок WHERE Формула.
Значением выражения является отношение, тело которого определяется формулой, а набор атрибутов и их имена - целевым списком. На основе рассмотренного исчисления построен язык SQL.
8.3. Реляционное исчисление доменов
В этом исчислении переменные являются доменами. Например, в базе данных СОТРУДНИКИ-ОТДЕЛЫ можно говорить о доменных переменных ИМЯ (значения - допустимые имена) или НОМЕР (значения - допустимые номера сотрудников). Основным отличием исчисления доменов от исчисления кортежей является наличие дополнительного набора предикатов, позволяющих выражать так называемые условия членства.
Если R - это отношение с атрибутами a1, a2,..., an, то условие членства имеет вид
R (ai1: vi1, ai2: vi2,..., aim: vim) (m <= n), где vij - это либо константа, либо имя доменной переменной. Условие членства истинно в том и только в том случае, если в отношении R существует кортеж, содержащий указанные значения указанных атрибутов.
Во всем остальном формулы и выражения этих двух видов реляционного исчисления похожи. Реляционное исчисление доменов является основой для большинства языков запросов, основанных на использовании форм, в частности, для популярного табличного языка запросов к БД Query-by-Example ("запрос по образцу").
Лекция 9. Язык SQL. Часть 1.