ВУЗ: Не указан
Категория: Не указан
Дисциплина: Не указана
Добавлен: 07.11.2023
Просмотров: 413
Скачиваний: 6
ВНИМАНИЕ! Если данный файл нарушает Ваши авторские права, то обязательно сообщите нам.
4.1.3. Реляционное исчисление доменов
В реляционном исчислении с переменными на доменах используются те же операторы, что и в реляционном исчислении с переменными-кортежами.
Атомы формул могут быть двух типов [11, 17].
1. R(x
1
x
2
...x
k
), где R – k-арное отношение; х
i
- константа или переменная на некотором домене.
Атом R(x
1
x
2
...x
k
) указывает, что значения тех x
i
, которые являются переменными, должны быть выбраны так, чтобы (x
1
x
2
...x
k
) было кортежем отношения R.
2. xθy, где х и у – константы или переменные на некотором домене, θ – оператор сравнения.
Атом хθу указывает, что х и у представляют собой значения, при которых истинно xθy.
Формулы в реляционном исчислении с переменными на доменах также используют логические связки
∧
,
∨
,
¬
и кванторы (
∀
x), (
∃
х), где х – переменная на домене. Аналогично используются понятия свободных и связанных переменных.
Реляционное исчисление с переменными на доменах имеет вид где φ – формула, обладающая тем свойством, что только ее свободные переменные на доменах являются различными переменными x
1
, x
2
, ..., x
k
. Например, выражение имеет место для бинарных отношений R
1
и R
2
и означает множество кортежей в R
1
,таких, что ни один из их компонентов не является первым компонентом какого-либо кортежа отношения R
2
.
С целью учета ограничения – конечности реальных отношений – аналогично вводятся безопасные выражения.
Реляционное исчисление с переменными на доменах называется безопасным, если выполняются следующие условия:
1) из истинности φ(х
1
, х
2
, ..., x
k
) следует, что x
i
принадлежит D(φ);
2) если (
∃
u)(φ
1
(u)) является подформулой φ, то из истинности φ
1
(u), следует, что и принадлежит D(φ);
3) если (
∀
u)(φ
1
(u)) является подформулой φ, то из истинности φ
1
(u), следует, что и не принадлежит D(φ
).
Выражение исчисления с переменными на доменах, эквивалентное заданному выражению исчисления с переменными-кортежами {t |φ(t)}, строится следующим образом:
1) если t является кортежем арности k, то вводится k новых переменных на доменах t
1
, t
2
, ..., t
k
;
2) атомы R(t) заменяются атомами R(t
1
, t
2
, ..., t
k
);
3) каждое свободное вхождение t[i]заменяется на t
i
;
4) для каждого квантора (
∃
u) или (
∀
u) вводится т новых переменных на доменах u
1
, и
2
, ..., и
т
, где т –
арность кортежа и. В области действия этой кванти-фикации выполняются замены:
5) выполняется построение выражения где φ’ – это φ, в которой выполнены соответствующие замены.
Например, {t
R
1
(t)
∨
R
2
(t)}перепишется так:
В реляционном исчислении с переменными на доменах существуют следующие две теоремы.
92
Теорема 4.2. Для каждого безопасного выражения реляционного исчисления с переменными-
кортежами существует эквивалентное безопасное выражение реляционного исчисления с
переменными на доменах [17].
Теорема 4.3. Для каждого безопасного выражения реляционного исчисления с переменными на
доменах существует эквивалентное ему выражение реляционной алгебры [17].
Примером реального языка запросов, реализующего реляционное исчисление с переменными на доменах, является QBE. Это графический язык, предоставляющий пользователю графическое отображение структуры отношения. Пользователь создает некий образец желаемого результата, а система возвращает затребованные данные в указанном формате.
4.1.4. Сравнение теоретических языков
Рассмотренные выше три абстрактных языка запросов служат основой реальных языков манипулирования данными реляционных систем.
Каждый из трех рассмотренных языков эквивалентен по своей выразительности двум другим.
Однако языки исчисления – это непроцедурные языки, поскольку их средствами можно выразить все, что необходимо и не обязательно указывать, как это получить (выражение в исчислении описывает лишь свойства желаемого результата, фактически не указывая, как его получить). Выражение реляционной алгебры, напротив, специфицируют конкретный порядок выполнения операций.
В первом случае определение наиболее эффективного порядка вычисления для реализации запроса пользователя выполняется транслятором или интерпретатором. Во втором случае пользователь обычно сам должен выполнить оптимизацию своего запроса при его формулировке. Однако, например, в соответствии с теоремой 1 транслятор на первом шаге трансляции запроса может выполнить преобразование алгебраического выражения в эквивалентное выражение исчисления и далее определить эффективный порядок вычислений [7, 17].
В общем случае языки манипулирования данными выходят за рамки теоретических языков, поскольку для обработки данных требуются операции, выходящие за рамки возможностей реляционного исчисления. Это прежде всего следующие команды: включить данные; модифицировать данные; удалить данные. Кроме этих операций обычно представляются следующие дополнительные возможности:
арифметические вычисления и сравнения могут включаться в формулы селекции реляционных алгебраических выражений или в атомы в выражениях реляционного исчисления;
команды печати;
агрегатные функции – функции, применяемые к столбцам отношений, в результате выполнения которых вычисляется одна-единственная величина, например максимальное или минимальное значение, сумма, среднее.
Так как реальные языки могут реализовывать функции, не имеющие аналогов ни в реляционной алгебре, ни в реляционном исчислении, то в действительности они являются более чем полными.
Причем, полным считается язык, в котором реализуются все возможности реляционного исчисления или реляционной алгебры.
Перспективной категорией языков запросов являются языки четвертого поколения (4-generation languages – 4GL), которые позволяют создавать полностью готовое и соответствующее требованиям заказчика прикладное приложение с помощью ограниченного набора команд и в то же время предоставляют дружественную по отношению к пользователю среду разработки, чаще всего построенную на использовании команд меню. В некоторых системах даже используются некоторые разновидности естественного языка, т.е. ограниченной версии обычного английского языка, который иногда называется языком пятого поколения (5GL) [7].
4.2. Определение реляционной полноты
Пусть реляционная база данных содержит множество отношений R{R
1
, R
2
, ..., R
n
}, а множество C(R)
представляет собой множество отношений, полученных из R спомощью операций реляционной
93
алгебры. Множество C(R) отражает все связи, имеющиеся в базе данных. Говорят, что язык обладает реляционной полнотой, если он может охватить все связи, представленные C(R). Это означает, что язык имеет такую же выразительную мощность, как реляционная алгебра и реляционное исчисление [11].
Для обеспечения реляционной полноты при реализации языка необходимы две следующие операции
[11]:
1) операция присваивания, т.е. возможность создавать новые отношения для хранения результатов операций реляционной алгебры, являющихся также отношениями. R
1
←
R
2
*R
3
означает, что результат соединения отношений R
2
и R
3
помещается во вновь созданное отношение R
1
;
2) операция транзитивного замыкания, допускающая рекурсию или вложенность операций реляционной алгебры для построения выражений произвольной сложности. Например, выражение содержит вложенные выражения и присваивание, необходимые для получения результата.
Для обеспечения реляционной полноты при реализации языка необходимы две следующие операции
[11]:
1) операция присваивания, т.е. возможность создавать новые отношения для хранения результатов операций реляционной алгебры, являющихся также отношениями. R
1
←
R
2
*R
3
означает, что результат соединения отношений R
2
и R
3
помещается во вновь созданное отношение R
1
;
2) операция транзитивного замыкания, допускающая рекурсию или вложенность операций реляционной алгебры для построения выражений произвольной сложности. Например, выражение содержит вложенные выражения и присваивание, необходимые для получения результата.
1 ... 5 6 7 8 9 10 11 12 ... 20
ГЛАВА 5. РАСПРЕДЕЛЕННЫЕ БАЗЫ ДАННЫХ И СУБД
Технология распределенных баз данных, получившая в настоящее время широкое распространение, способствует обратному переходу от централизованной обработки данных к децентрализованной.
Создание технологии систем управления распределенными базами данных является одним самых больших достижений в области баз данных.
5.1. Основные определения, классификация распределенных систем
Основной причиной разработки систем, использующих базы данных, является стремление интегрировать все обрабатываемые в организации данные в единое целое и обеспечить к ним контролируемый доступ. Хотя интеграция и предоставление контролируемого доступа могут способствовать централизации, последняя не является самоцелью. На практике создание компьютерных сетей приводит к децентрализации обработки данных. Децентрализованный подход отражает организационную структуру компании, логически состоящую из отдельных подразделений, отделов, проектных групп и тому подобного, которые физически распределены по разным офисам, отделениям, предприятиям или филиалам, причем каждая отдельная единица имеет дело с собственным набором обрабатываемых данных [7, 9].
Разработка распределенных баз данных позволяет сделать данные, поддерживаемые каждым из существующих подразделений организации, общедоступными, обеспечив при этом их сохранение именно в тех местах, где они чаще всего используются. Подобный подход расширяет возможности совместного использования информации, одновременно повышая эффективность доступа к ней.
Распределенные системы призваны разрешить проблему островов информации. Базы данных иногда рассматривают как некие электронные острова, представляющие собой отдельные и, в общем случае, труднодоступные места, подобные удаленным друг от друга островам. Данное положение может являться следствием географической разобщенности, несовместимости используемой компьютерной архитектуры, несовместимости используемых коммутационных протоколов и т.д. Интеграция отдельных баз данных в одно логическое целое способна изменить подобное положение дел.
Распределенная база данных – набор логически связанных между собой разделяемых данных (и их описаний), которые физически распределены в некоторой компьютерной сети.
Распределенная СУБД – программный комплекс, предназначенный для управления распределенными базами данных и позволяющий сделать распределен-ность информации прозрачной для конечного пользователя.
Система управления распределенными базами данных (СУРБД) состоит из единой логической базы данных, разделенной на некоторое количество фрагментов. Каждый фрагмент базы данных сохраняется на одном или нескольких компьютерах, которые соединены между собой линиями связи и каждый из которых работает под управлением отдельной СУБД. Любой из сайтов способен независимо обрабатывать запросы пользователей, требующие доступа к локально сохраняемым данным (что создает определенную степень локальной автономии), а также способен обрабатывать данные, сохраняемые на других компьютерах сети.
94
Пользователи взаимодействуют с распределенной базой данных через приложения. Приложения могут быть классифицированы как те, которые не требуют доступа к данным на других сайтах
(локальные приложения), и те, которые требуют подобного доступа (глобальные приложения). В распределенной СУБД должно существовать хотя бы одно глобальное приложение, поэтому любая
СУРБД должна иметь следующие особенности [7].
Набор логически связанных разделяемых данных.
Сохраняемые данные разбиты на некоторое количество фрагментов.
Между фрагментами может быть организована репликация данных.
Фрагменты и их реплики распределены по различным сайтам.
Сайты связаны между собой сетевыми соединениями.
Работа с данными на каждом сайте управляется СУБД.
СУБД на каждом сайте способна поддерживать автономную работу локальных приложений.
СУБД каждого сайта поддерживает хотя бы одно глобальное приложение.
Нет необходимости в том, чтобы на каждом из сайтов системы существовала своя собственная локальная база данных, что и показано на примере топологии СУРБД, представленной на рис. 5.1.
Рис. 5.1. Топология системы управления распределенной базой данных
Из определения СУРБД следует, что для конечного пользователя распределенность системы должна быть совершенно прозрачна (невидима). Другими словами, от пользователей должен быть полностью скрыт тот факт, что распределенная база данных состоит из нескольких фрагментов, которые могут размещаться на различных компьютерах и для которых, возможно, организована служба репликации данных.
Назначение обеспечения прозрачности состоит в том, чтобы распределенная система внешне вела себя точно так, как и централизованная. В некоторых случаях это требование называют основным
принципом построения распределенных СУБД [7]. Данный принцип требует предоставления конечному пользователю существенного диапазона функциональных возможностей, но, к сожалению, одновременно ставит перед программным обеспечением СУРБД множество дополнительных задач.
Очень важно понимать различия, существующие между распределенными СУБД и распределенной обработкой данных.
Распределенная обработка – обработка с использованием централизованной базы данных, доступ к которой может осуществляться с различных компьютеров сети.
Ключевым моментом в определении распределенной базы данных является утверждение, что система работает с данными, физически распределенными в сети. Если данные хранятся централизованно, то даже в том случае, когда доступ к ним обеспечивается для любого пользователя в сети, данная система просто поддерживает распределенную обработку, но не может рассматриваться как распределенная СУБД.
Кроме того, следует четко понимать различия, существующие между распределенными и параллельными СУБД.
Параллельная СУБД – система управления базой данных, функционирующая с использованием нескольких процессоров и устройств жестких дисков, что позволяет ей (если это возможно) распараллеливать выполнение некоторых операций с целью повышения общей производительности
95