 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Реляционное исчисление кортежей
В реляционном исчислении кортежей задача состоит в нахождении таких кортежей, для которых предикат является истинным.
Выражение реляционного исчисления с переменными-кортежами записывается в виде
{ t | j(t)},
где t – свободная переменная-кортеж, обозначающая кортеж фиксированной длины (если необходимо указать арность кортежа, то используют запись t(i); i – арность кортежа t); j – некоторая формула, построенная по специальным правилам.
Например, выражение { t | R 1(t)Ú R 2(t)}, где в качестве формулы выступает конструкция R 1(t)Ú R 2(t), означает, что необходимо получить множество всех кортежей t, причем таких кортежей, которые принадлежат отношениям R 1 или R 2. Формула (R 1(t)Ú R 2(t)) имеет смысл только тогда, когда отношения R 1 и R 2 имеют одинаковую арность, поскольку переменная-кортеж t задана как переменная фиксированной длины. Выражение { t | R 1(t)Ú R 2(t)} эквивалентно операции объединения (R 1È R 2) реляционной алгебры.
Формулы в реляционном исчислении строятся из атомов и совокупности арифметических и логических операторов.
Атомы формул могут быть трех типов:
1) R (t), где R – имя отношения. Этот атом означает, что t – это кортеж в отношении R;
2) s [ i ]q u [ j ], где s и u – переменные-кортежи; q – арифметический оператор (<, >, =, £, ³, ¹); i, j – номера или имена необходимых компонентов (столбцов) в соответствующих кортежах; s [ i ] – i -тый компонент в кортеже-переменной s; u [ j ] – j -тый компонент в кортеже-переменной u. Например, атом (s [3]³ u [5]) означает, что третий компонент переменной s больше или равен пятому компоненту переменной u;
3) s [ i ]q a или a q s [ i ], где а – константа. Например, атом (s [4]=70), означает, что четвертая компонента переменной-кортежа s равна 70.
При записи формул используется понятие свободных и связанных переменных-кортежей, что определяется характером использования в формуле кванторов; " - квантор всеобщности (общности), читается – все, всякий, каков бы ни был и т.п.; $ - квантор существования, читается – некоторые, хотя бы один существует и т.п.
Вхождение переменной t в формулу j связано, если в j оно находится в подформуле, начинающейся квантором " или $, за которым непосредственно следует переменная t и о котором говорят, что он связывает переменную t. В остальных случаях вхождения переменной t в формулу j свободны. Например, в формуле
(" x)(R (x, y)Ú($ y)(U (x, y, z)Ù Q (x, y)))Ú(" x)($ r)(U (x, y, r)Ù($ x) F (x))
все вхождения переменной x связаны, первое и последнее вхождения y свободны, остальные вхождения переменной y связаны, все вхождения переменной z свободны, единственное вхождение переменной r связано.
Кванторы в реляционном исчислении играют ту же роль, что декларации в языке программирования. Понятие свободной переменной аналогично понятию глобальной переменной, описанной вне текущей процедуры. Понятие связанной переменной аналогично понятию локальной переменной, описанной в текущей процедуре.
Аналогично тому, как не все возможные комбинации букв алфавита образуют правильные слова, так и в реляционном исчислении не каждая последовательность формул является допустимой. Допустимыми формулами могут быть только недвусмысленные и небессмысленные последовательности.
Правильно построенные формулы определяются рекурсивно следующим образом.
1. Каждый атом – это формула. Все вхождения переменных-кортежей, упомянутые в атоме, являются свободными.
2. Если j1 и j2 – формулы, то выражения j1Ùj2 (утверждает, что j1 и j2 истинны), j1Új2 (утверждает, что j1 или j2, или обе истинны), Øj1 (утверждает, что j1 не истинна), также являются формулами.
Экземпляры переменных-кортежей – свободные или связанные в формулах (j1Ùj2), (j1Új2) и (Øj1) так же, как и в j1 и j2. Таким образом, свободными (связанными) являются те и только те вхождения переменных, которые происходят от свободных (связанных) вхождений переменных j1 и j2. Некоторое вхождение переменной может быть связанным в j1, например, в то время как другое – свободным в j2 и т.п.
3. Если j – формула, то (" s)(j) – также формула. Свободные вхождения переменной s в формуле j становятся связанными квантором (" s) в формуле (" s)(j). Формула (" s)(j) утверждает, что при подстановке любого кортежа подходящей арности вместо свободных вхождений s формула становится истинной.
4. Если j – формула, то ($ s)(j) – также формула. Свободные вхождения переменной s в формуле j также становятся связанными квантором ($ s) в формуле ($ s)(j). Формула ($ s)(j) утверждает, что существует значение s, при подстановке которого вместо всех свободных вхождений s в формулу j эта формула становится истинной.
Например, формула ($ s)(R (s)) означает, что отношение не пусто, т.е. существует некоторый кортеж s, принадлежащий R.
5. Формулы могут при необходимости заключаться в скобки. Используется следующий порядок старшинства:
- арифметические операторы сравнения;
- кванторы " и $;
- Ù, Ú, Ø.
6. Ничто иное не является формулой.
В качестве примера можно записать выражение реляционного исчисления на переменных-кортежах, соответствующее операции проекции в реляционной алгебре:
{ t (k)| ($ u)(R (u)Ù t [1]= u [ i 1]Ù...Ù t [ k ]= u [ ik ])}.
Введем ограничения на конечность реальных отношений в БД, чтобы исключить возможность формирования выражений типа { t |- R (t)}, не имеющих смысла. Это выражение обозначает все возможные, не принадлежащие R кортежи, арность которых согласуется с t.
С этой целью в реляционном исчислении рассматривают только безопасные выражения { t |j(t)}, для которых выполняется условие, что каждый компонент (элемент столбца) любого кортежа t, удовлетворяющего j(t) является элементом некоторого множества элементов D (j). Множество D (j) определяется как функция фактических отношений, которые указываются в j(t), и констант, присутствующих в формуле j(t) и элементов кортежей тех отношений, которые указаны в j(t). Так как все отношения в БД предполагаются конечными, то и множество D (j) – конечно:
D (j)= { a 1.j}È{ a 2.j}È…È{ an .j}Èp1(R 1)Èp2(R 1)È…Èp k (Rn),
где a 1.j, a 2.j, …, an .j – константы, встретившиеся в формуле j(t); p1(R 1), …, p k (Rn) – проекции кортежей фактических отношений R 1, …, Rn, встретившихся в формуле j(t) (в данном случае – компоненты кортежей).
При таком определении множества D (j) справедливо следующее:
D (j1(t)Új2(t))= D (j1)È D (j2),
D (j1(t)Ùj2(t))= D (j1)È D (j2),
D (j1(t)ÙØj2(t))= D (j1)È D (j2) и т.п.
Например, если задано выражение { t | c Ú R (t)}, где R – бинарное отношение, то
D (j)= { c }Èp1(R)Èp2(R).
Реляционное исчисление является безопасным, если выполнятся следующие условия:
1) из истинности j(t) следует, что каждый компонент кортежа t принадлежит D (j);
2) для любой подформулы вида ($ u)(j1(u)), входящей в состав j, из истинности j1(u) следует, что u принадлежит D (j1);
3) для любой подформулы вида (" u)(j1(u)), входящей в состав j, из истинности j1(u) следует, что u не принадлежит D (j1), или же, что то же самое, из истинности Øj1(u) следует, что u принадлежит D (j1).
При выполнении этих условий выражение { t |j(t)} является безопасным. Выражению (" u)(j1(u)) эквивалентно выражение Ø($ u)(Øj1(u)).
На основании вышеизложенного можно утверждать, что если формула j(t) такова, что любая ее подформула вида ($ u)(j i (t)) или (" u)(j j (t)) безопасна, то безопасно каждое выражение вида { t | R (t)Ùj(t)}. Действительно, любой кортеж, удовлетворяющий формуле (R (t)Ùj(t)), принадлежит в соответствии с этой формулой отношению R. Следовательно, каждый из его компонентов будет принадлежать также и множеству элементов D (R (t)Ùj(t)). Тогда в силу выполнения условия 1 (выполнение условий 2 и 3 задано как исходная предпосылка) выражение { t | R (t)Ùj(t)} – безопасное. Если в j(t) найдется хотя бы одна из подформул вида ($ u)(j i (t)) или (" u)(j j (t)), которая окажется не безопасной, то тогда и выражение { t | R (t)Ùj(t)} не будет безопасным. Если в формуле j(t) вообще отсутствуют подформулы вида ($ u)(j i (t)) или (" u)(j j (t)) – или соответствующие им эквивалентные Ø(" u)(Øj i (t)) или Ø($ u)(Øj j (t)), - то выражение { t | R (t)Ùj(t)} всегда является безопасным.
Например, если j(t)=Ø R 2(t), то получим безопасное выражение { t | R 1(t)Ù Ø R 2(t)}, соответствующее операции разности отношений в реляционной алгебре (R 1- R 2).
Безопасным является также выражение { t | R (t)}, соответствующее выражению R (точнее – переменной R, обозначающей отношение).
В реляционном исчислении на переменных-кортежах доказана теорема, устанавливающая эквивалентность безопасных выражений в исчислении операциям реляционной алгебры.
Теорема 7.1. Если Е – выражение реляционной алгебры, то существует эквивалентное ему безопасное выражение в реляционном исчислении с переменными-кортежами.
Для основных операций реляционной алгебры укажем следующие соответствующие выражения реляционного исчисления на переменных-кортежах.
1. Операции объединения (R 1È R 2) соответствует выражение
{ t | R 1(t)Ú R 2(t)}.
2. Операции разности (R 1- R 2) соответствует выражение
{ t | R 1(t)ÙØ R 2(t)}.
Рассматривается все множество кортежей t, таких, что t принадлежит R 1 и не принадлежит R 2.
3. Операции декартова произведения (R 1Ä R 2) соответствует выражение
{ t ( k + m )| ($ u)($ v)(R 1(u)Ù R 2(v)Ù t [1]= u [1]Ù…Ù t [ k ]= u [ k ]Ù t [ k +1]= v [1]Ù…Ù t [ k + m ]= v [ m ])}.
Рассматривается все множество кортежей t арности (k + m), таких, что существует кортеж u, принадлежащий R 1, и существует кортеж v, принадлежащий R 2, причем k первых компонентов кортежа t образуют компоненты кортежа u, а следующие m компонентов кортежа t образуют компоненты кортежа v.
4. Операции проекции соответствует выражение
{ t (k)| ($ u)(R 1Ù t [1]= u [ i 1]Ù…Ù t [ k ]= u [ ik ])}.
5. Операции селекции соответствует выражение { t | R (t)Ù F¢ }, где F¢ – это выражение F, в котором каждый операнд, обозначающий компонент i, заменен на t [ i ].
Несмотря на то, что реляционное исчисление является достаточно сложным с точки зрения освоения и использования, тем не менее, его непроцедурная природа считается весьма перспективной и это стимулирует поиск других, более простых в употреблении непроцедурных методов. Подобные исследования привели к появлению двух категорий реальных реляционных языков:
- языков на основе преобразований;
- графических языков.
Языки на основе преобразований являются классом непроцедурных языков, которые используют отношения для преобразования исходных данных к требуемому виду. Эти языки предоставляют простые в употреблении структуры для получения результата. Примером реального языка на основе преобразований, реализующего реляционное исчисление с переменными-кортежами, является язык запросов SQL.
Поиск по сайту: