 |
АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция
Реляционное исчисление доменов
В реляционном исчислении с переменными на доменах используются те же операторы, что и в реляционном исчислении с переменными-кортежами.
Атомы формул могут быть двух типов.
1. R (x 1 x 2… xk), где R – k -арное отношение; хi – константа или переменная на некотором домене.
Атом R (x 1 x 2… xk) указывает, что значения тех хi, которые являются переменными, должны быть выбраны так, чтобы (x 1 x 2… xk) было кортежем отношения R.
2. x q y, где х и у – константы или переменные на некотором домене, q –оператор сравнения.
Атом x q y указывает, что х и у представляют собой значения, при которых истинно x q y.
Формулы в реляционном исчислении с переменными на доменах также используют логические связки Ù, Ú, Ø и кванторы (" x), ($ x), где х – переменная на домене. Аналогично используются понятия свободных и связанных переменных.
Реляционное исчисление с переменными на доменах имеет вид
{ x 1 x 2… xk | j(x 1, x 2, …, xk)},
где j – формула, обладающая тем свойством, что только ее свободные переменные на доменах являются различными переменными x 1, x 2, …, xk.
Например, выражение
{ x 1 x 2 | R 1(x 1 x 2)Ù(" y)(Ø R 2(x 1 y)ÙØ R 2(x 2 y))}
имеет место для бинарных отношений R 1 и R 2 и означает множество кортежей в R 1, таких, что ни один из их компонентов не является первым компонентом какого-либо кортежа отношения R 2.
С целью учета ограничения – конечности реальных отношений – аналогично вводятся безопасные выражения.
Реляционное исчисление с переменными на доменах называется безопасным, если выполняются следующие условия:
1) из истинности j(x 1, x 2, …, xk) следует, что хi принадлежит D (j);
2) если ($ u)(j1(u)) является подформулой j, то из истинности j1(u), следует, что u принадлежит D (j);
3) если (" u)(j1(u)) является подформулой j, то из истинности j1(u), следует, что u не принадлежит D (j).
Выражение исчисления с переменными на доменах, эквивалентное заданному выражению исчисления с переменными-кортежами { t |j(t)}, строится следующим образом:
1) если t является кортежем арности k, то вводится k новых переменных на доменах t 1, t 2, …, tk;
2) атомы R (t) заменяются атомами R (t 1, t 2, …, tk);
3) каждое свободное вхождение t [ i ] заменяется на ti;
4) для каждого квантора ($ u) или (" u) вводится m новых переменных на доменах u 1, u 2, …, um, где m – арность кортежа u. В области действия этой квантификации выполняются замены:
R (u) на R (u 1 u 2… um),
u [ i ] заменяется на ui,
($ u) на ($ u 1)($ u 1)…($ um),
(" u) на (" u 1)(" u 1)…(" um);
5) выполняется построение выражения
{ t 1 t 2… tk | j¢(t 1, t 2, …, tk)},
где j¢ – это j, в которой выполнены соответствующие замены.
Например, { t | R 1(t)Ú R 2(t)} перепишется так:
{ t 1 t 2… tk | R 1(t 1, t 2, …, tk)Ú R 2(t 1, t 2, …, tk)}.
В реляционном исчислении с переменными на доменах существуют следующие две теоремы.
Теорема 7.2. Для каждого безопасного выражения реляционного исчисления с переменными-кортежами существует эквивалентное безопасное выражение реляционного исчисления с переменными на доменах.
Теорема 7.3. Для каждого безопасного выражения реляционного исчисления с переменными на доменах существует эквивалентное ему выражение реляционной алгебры.
Примером реального языка запросов, реализующего реляционное исчисление с переменными на доменах, является QBE. Это графический язык, предоставляющий пользователю графическое отображение структуры отношения. Пользователь создает некий образец желаемого результата, а система возвращает затребованные данные в указанном формате.
3. Сравнение алгебраических языков и языков исчисления (≈10 мин).
Рассмотренные выше три абстрактных языка запросов служат основой реальных языков манипулирования данными реляционных систем.
Каждый из трех рассмотренных языков эквивалентен по своей выразительности двум другим. Однако языки исчисления – это непроцедурные языки, поскольку их средствами можно выразить все, что необходимо и не обязательно указывать, как это получить (выражение в исчислении описывает лишь свойства желаемого результата, фактически не указывая, как его получить). Выражение реляционной алгебры, напротив, специфицируют конкретный порядок выполнения операций.
В первом случае определение наиболее эффективного порядка вычисления для реализации запроса пользователя выполняется транслятором или интерпретатором. Во втором случае пользователь обычно сам должен выполнить оптимизацию своего запроса при его формулировке. Однако, например, в соответствии с теоремой 7.1 транслятор на первом шаге трансляции запроса может выполнить преобразование алгебраического выражения в эквивалентное выражение исчисления и далее определить эффективный порядок вычислений.
В общем случае языки манипулирования данными выходят за рамки теоретических языков, поскольку для обработки данных требуются операции, выходящие за рамки возможностей реляционного исчисления. Это, прежде всего следующие команды: включить данные; модифицировать данные; удалить данные. Кроме этих операций обычно представляются следующие дополнительные возможности:
- арифметические вычисления и сравнения могут включаться в формулы селекции реляционных алгебраических выражений или в атомы в выражениях реляционного исчисления;
- команды печати;
- агрегатные функции – функции, применяемые к столбцам отношений, в результате выполнения которых вычисляется одна-единственная величина, например максимальное или минимальное значение, сумма, среднее.
Так как реальные языки могут реализовывать функции, не имеющие аналогов ни в реляционной алгебре, ни в реляционном исчислении, то в действительности они являются более чем полными. Причем, полным считается язык, в котором реализуются все возможности реляционного исчисления или реляционной алгебры.
Перспективной категорией языков запросов являются языки четвертого поколения (4-generation languages – 4GL), которые позволяют создавать полностью готовое и соответствующее требованиям заказчика прикладное приложение с помощью ограниченного набора команд и в то же время предоставляют дружественную по отношению к пользователю среду разработки, чаще всего построенную на использовании команд меню. В некоторых системах даже используются некоторые разновидности естественного языка, т.е. ограниченной версии обычного английского языка, который иногда называется языком пятого поколения (5GL).
Поиск по сайту: