Реляционное исчисление кортежей
В выражениях реляционной алгебры всегда явно задается некий порядок выполнения запроса. В реляционном же исчислении указывается что необходимо извлечь, а не как.
Реляционное исчисление никак не связано с дифференциальным и интегральным исчислениями в математике, а его название произошло от части символьной логики, которая называется логикой предикатов.
В логике первого порядка или теории исчисления предикатов под предикатом подразумевается истинностная функция с аргументами. При подстановке вместо аргументов значений, функция становится выражением, называемым суждением, которое может быть истинным или ложным. Например, предложения «студент Шепе-лявцев учится на третьем курсе вуза» и «средний балл успеваемости студента Шепелявцева выше, чем у студента Мамаева» являются суждениями, поскольку можно определить их истинность или ложность. В первом случае функция «учится на третьем курсе вуза» имеет один аргумент («студент Шепелявцев»), а во втором случае функция «средний балл выше» имеет два аргумента («студент Шепелявцев» и «студент Мамаев»).
Если предикат содержит переменную, например в виде «x учится на третьем курсе вуза», то у этой переменной должна быть область определения. При подстановке вместо переменной x одних значений из ее области определения данное суждение может оказаться истинным, а при подстановке других – ложным.
Если P – предикат, то множество всех значений переменной x, при которых суждение Р становится истинным, можно символически записать следующим образом:
{x| P(x)}.
Предикаты могут соединяться с помощью логических операторов ?, ?, ¬ с образованием составных предикатов.
В реляционном исчислении кортежей задача состоит в нахождении таких кортежей, для которых предикат является истинным.
Выражение реляционного исчисления с переменными-кортежами записывается в виде [17]
{t| ?(t)},
где t – свободная переменная-кортеж, обозначающая кортеж фиксированной длины (если необходимо указать арность кортежа, то используют запись t(i); i-арность кортежа t); ? – некоторая формула, построенная по специальным правилам.
Например, выражение {t| R1(t) ?R2(t)}, где в качестве формулы выступает конструкция R1(t) ?R2(t), означает, что необходимо получить множество всех кортежей t, причем таких кортежей, которые принадлежат отношениям R1 или R2. Формула (R1(t) ?R2(t))) имеет смысл только тогда, когда отношения R1 и R2 имеют одинаковую арность, поскольку переменная-кортеж t задана как переменная фиксированной длины. Выражение { t| R1(t) ?R2(t)} эквивалентно операции объединения (R1
реляционной алгебры.
Формулы в реляционном исчислении строятся из атомов и совокупности арифметических и логических операторов.
Атомы формул могут быть трех типов [17]:
1) R(t), где R – имя отношения. Этот атом означает, что t – это кортеж в отношении R;
2) s[i]?u[j], где s и u - переменные-кортежи; ? – арифметический оператор (<, >, =, ?, ?, ?); i, j – номера или имена необходимых компонентов (столбцов) в соответствующих кортежах; s[i] – i-тый компонент в кортеже-переменной s; u[j] - j-тый компонент в кортеже-переменной и. Например, атом (s[3] ? u[5]) означает, что третий компонент переменной s больше или равен пятому компоненту переменной u;
3) s[i]?a или a?s[i], где a – константа. Например, атом (s[4]=70), означает, что четвертая компонента переменной-кортежа s
равна 70.
При записи формул используется понятие свободных и связанных переменных-кортежей, что определяется характером использования в формуле кванторов;
Вхождение переменной t в формулу ? связано, если в ? оно находится в подформуле, начинающейся квантором
все вхождения переменной x связаны, первое и последнее вхождения y свободны, остальные вхождения переменной y связаны, все вхождения переменной z свободны, единственное вхождение переменной r связано.
Кванторы в реляционном исчислении играют ту же роль, что декларации в языке программирования. Понятие свободной переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие связанной переменной аналогично понятию локальной переменной, описанной в текущей процедуре.
Аналогично тому, как не все возможные комбинации букв алфавита образуют правильные слова, так и в реляционном исчислении не каждая последовательность формул является допустимой. Допустимыми формулами могут быть только недвусмысленные и небессмысленные последовательности.
Правильно построенные формулы определяются рекурсивно следующим образом [11, 17].
1. Каждый атом – это формула. Все вхождения переменных-кортежей, упомянутые в атоме, являются свободными.
2. Если ?1 и ?2 - формулы, то выражения ?1 ??2
(утверждает, что ?1 и ?2 истинны), ?1
??2
(утверждает, что ?1 или ?2, или обе истинны), ¬?1 (утверждает, что ?1 не истинна), также являются формулами.
Экземпляры переменных-кортежей – свободные или связанные в формулах (?1 ??
2), (?1 ??
2) и (¬?1) так же, как и в ?1 и ?2. Таким образом, свободными (связанными) являются те и только те вхождения переменных, которые происходят от свободных (связанных) вхождений переменных ?1 и ?2. Некоторое вхождение переменной может быть связанным в ?1 например, в то время как другое – свободным в ?2 и т.п.
3. Если ? – формула, то (
в формуле ? становятся связанными квантором (
4. Если ? – формула, то (
в формулу ? эта формула становится истинной.
Например, формула (
5. Формулы могут при необходимости заключаться в скобки. Используется следующий порядок старшинства:
§ арифметические операторы сравнения;
§ кванторы
§ ?, ?, ¬.
6. Ничто иное не является формулой.
В качестве примера можно записать выражение реляционного исчисления на переменных-кортежах, соответствующее операции проекции в реляционной алгебре:
Введем ограничения на конечность реальных отношений в БД, чтобы исключить возможность формирования выражений типа {t|-R(t)}, не имеющих смысла. Это выражение обозначает все возможные, не принадлежащие R кортежи, арность которых согласуется с t.
С этой целью в реляционном исчислении рассматривают только безопасные выражения {t|?(t)}, для которых выполняется условие, что каждый компонент (элемент столбца) любого кортежа t, удовлетворяющего ?(t) является элементом некоторого множества элементов D(?). Множество D(?) определяется как функция фактических отношений, которые указываются в ?(t), и констант, присутствующих в формуле ?(t) и элементов кортежей тех отношений, которые указаны в ?(t). Так как все отношения в БД предполагаются конечными, то и множество D(?) – конечно:
D(?)={a1.?}
где a1.?, a2.?, ..., an.? – константы, встретившиеся в формуле ?(t); ?1(R1), …, ?k(Rn) – проекции кортежей фактических отношений R1, ..., Rn, встретившихся в формуле ?(t) (в данном случае – компоненты кортежей).
При таком определении множества D(?) справедливо следующее:
D(?1(t) ??2(t))= D(?1)
D(?1(t) ??2(t))= D(?1)
D(?1(t) ?¬?2(t))= D(?1)
Например, если задано выражение {t|c ?R(t)}, где R – бинарное отношение, то
D(?)={c}
Реляционное исчисление является безопасным, если выполнятся следующие условия:
1) из истинности ?(t) следует, что каждый компонент кортежа t принадлежит – D(?);
2) для любой подформулы вида (
3) для любой подформулы вида (
При выполнении этих условий выражение {t|?(t)} является безопасным. Выражению (
На основании вышеизложенного можно утверждать, что если формула ?(t) такова, что любая ее подформула вида (
{t|R(t) ??(t)}. Действительно, любой кортеж, удовлетворяющий формуле (R(t) ??(t)), принадлежит в соответствии с этой формулой отношению R. Следовательно, каждый из его компонентов будет принадлежать также и множеству элементов D(R(t) ??(t)). Тогда в силу выполнения условия 1 (выполнение условий 2 и 3 задано как исходная предпосылка) выражение { t|R(t) ??(t)} – безопасное. Если в ?(t) найдется хотя бы одна из подформул вида (
Например, если ?(t)=¬R2(t) то получим безопасное выражение {t|R1(t) ?¬R2(t)} соответствующее операции разности отношений в реляционной алгебре (R1–R2).
Безопасным является также выражение {t|R(t)}, соответствующее выражению R (точнее – переменной R, обозначающей отношение).
В реляционном исчислении на переменных- кортежах доказана теорема, устанавливающая эквивалентность безопасных выражений в исчислении операциям реляционной алгебры.
Теорема 4.1. Если E - выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение в реляционном исчислении с переменными-кортежами [17].
Для основных операций реляционной алгебры укажем следующие соответствующие выражения реляционного исчисления на переменных-кортежах.
1. Операции объединения (R1
соответствует выражение
соответствует выражение
{t|R1(t) ?R2(t)}.
2. Операции разности (R1-R2) соответствует выражение
соответствует выражение
{t|R1(t) ?¬R2(t)}.
Рассматривается все множество кортежей t, таких, что t принадлежит R1 и не принадлежит R2.
3. Операции декартова произведения (R1
{t(k+m)|(
=u[k] ?t[k+1]=v[1] ?… ?t[k+m]=v[m])}.
Рассматривается все множество кортежей t арности (k+m), таких, что существует кортеж u, принадлежащий R1, и существует кортеж v, принадлежащий R2, причем k первых компонентов кортежа t образуют компоненты кортежа и, а следующие m компонентов кортежа t образуют компоненты кортежа v.
4. Операции проекции соответствует выражение
{t(k)|(
?t[1]=u[i1] ?… ?t[k]= u[ik])}
5. Операции селекции соответствует выражение {t|R(t) ?F'}, где F' – это выражение F, в котором каждый операнд, обозначающий компонент i, заменен на t[i].
Несмотря на то, что реляционное исчисление является достаточно сложным с точки зрения освоения и использования, тем не менее, его непроцедурная природа считается весьма перспективной и это стимулирует поиск других, более простых в употреблении непроцедурных методов. Подобные исследования привели к появлению двух категорий реальных реляционных языков:
– языков на основе преобразований;
– графических языков.
Языки на основе преобразований являются классом непроцедурных языков, которые используют отношения для преобразования исходных данных к требуемому виду. Эти языки предоставляют простые в употреблении структуры для получения результата. Примером реального языка на основе преобразований, реализующего реляционное исчисление с переменными-кортежами, является язык запросов SQL.
