Лекции по Базам данных. лекции. Развитие технологий обработки данных
 Скачать 0.53 Mb.
|
|
Дополнительные операции реляционной алгебры. Состав операций реляционной алгебры является избыточным, поскольку некоторые из них могут быть получены через остальные операции с использованием определенных соотношений. Но Кодд сознательно ввел эту избыточность в свою алгебру, учитывая то, что эти соотношения не так уж просты и их использование, как правило, довольно-таки усложняет реляционные выражения. Итак, к дополнительным операциям относятся те операции реляционной алгебры, которые можно выражать через основные операции. Пересечение Это четвертая булева бинарная операция над отношениями. Пусть имеются два отношения r и s, тогда отношение t =  называется пересечением r и s, если каждый кортеж, принадлежащий t, одновременно принадлежит r и s. Операция применяется к отношениям одной арности. Справедлива следующая формула: t= . Применительно к отношениям r и s получим:
Естественное соединение Естественное соединениесоздает новое отношение из двух существующих. Новое отношение формируется с помощью сцепления кортежей первого отношения с кортежами второго отношения. При выполнении этой операции указывается, какой атрибут первого отношения, и какой атрибут второго отношения используются для сцепления кортежей. Пусть даны отношения r(R) и s(S). Необходимо осуществить соединение этих отношений, используя атрибут А отношения r и атрибут D отношения s. При таких условиях оператор выполняется следующим образом: просматриваются по порядку все кортежи отношения r, и для каждого кортежа анализируется значение атрибута А. Из отношения s выбираются кортежи, у которых значение атрибута D совпадает со значением А. Такие кортежи сцепляются. При этом в результирующее отношение равные атрибуты включаются только один раз. Записывается этот оператор так:
Соединение (Jоin) Пусть имеются два отношения r (X, Y) и s (Y, Z) и некоторое условие  , где X, Y, Z– непересекающиеся множества атрибутов и Y – множество атрибутов, общих для r и s, тогда отношение. называется -соединением r и s, если каждый кортеж, принадлежащий t, состоит из кортежей rи s, при выполненном условии . Справедлива следующая формула: , то есть -соединение представляет собой декартово произведение r и s, над которым выполнена селекция по условию .
Деление Деление – это также бинарная несимметричная операция для получения некоторого отношения из двух исходных, причем степень результирующего отношения не совпадает со степенью ни одного из операндов, а вычисляется как разность между степенью отношения-делимого и степенью отношения-делителя. Пусть имеются отношения r{Х, У) арности k1 и p(Z) арности k2, где Y и Z определены на одном домене, тогда отношение t =r?p арности k1 – k2 называется делением r на р, если любой кортеж из t вместе с любым кортежем из р образуют кортеж, имеющийся в r. Итак, k1 – арность r; k2 – арность р; k = k1 –k2 арность результирующего отношения. Причем k1 > k2 – всегда. Реляционное исчисление. Хотя реляционная алгебра и является основой нескольких языков запросов, следует отметить, что большинство работающих языков запросов все-таки основано на реляционном исчислении. Основной причиной такого положения является стремление пользователя, а значит, и разработчиков конкретных языков запросов по возможности облегчить процесс взаимодействия с базой данных. Реляционная алгебра – процедурная система, а это значит, что выражение реляционной алгебры задает набор операций над отношениями и порядок их выполнения. Реляционные исчисления – непроцедурные системы. Исчисления выражают только то, каким должен быть результат вычисления, но не то, каким образом проводить вычисления. Таким образом, базирующиеся на непроцедурных системах языки запросов освобождают пользователя от необходимости определять, как получить желаемый ответ, и пользователь может даже этого вовсе не знать. Эта обязанность возлагается на процессор языка запросов данной системы управления базой данных. Название реляционного исчисления происходит от исчисления предикатов в математической логике. Различают реляционное исчисление кортежей и реляционное исчисление доменов. Поскольку реляционное исчисление доменов сходно с реляционным исчислением кортежей за исключением того, что переменные принимают значения в доменах, а не являются кортежами, а исчисление кортежей используется чаще. В дальнейшем, когда речь будет идти о реляционном исчислении, будет подразумеваться именно реляционное исчисление кортежей. В то время как реляционная алгебра использует в качестве операндов отношения, реляционное исчисление кортежей строит свои выражения из кортежей. Реляционное исчисление определяет результат запроса в виде реляционного множества. Реляционное исчисление кортежей является, по сути, формализацией системы обозначений, предназначенной для образования множеств. В реляционном исчислении используются булевы операции (И, ИЛИ, НЕ) над условиями, которые могут быть истинными или ложными. В нем также используются кванторы существования и всеобщности, означающие, соответственно, что элемент определенного типа существует или что условие истинно для каждого элемента определенного типа. Хотя в реляционном исчислении используется совершенно иной подход, чем в реляционной алгебре, тем не менее эти два языка логически эквивалентны. Это означает, что любой запрос, который можно выполнить на одном языке, можно сформулировать и выполнить на другом. Рассмотрим отношение:
Запрос: Какие детали имеют вес, равный 2? В реляционной алгебре для выполнения этого запроса необходимо использовать алгебраическое выражение, которое должно содержать следующие операции: операцию Выборнад отношением r; результатом ее применения к отношению r является другое отношение, которое представляет собой подмножество кортежей отношения г со значением, равным 2 в атрибуте Вес:
проецирование результата предыдущей операции на атрибут Назв_дет. Окончательный результат запроса будет выглядеть следующим образом:
В реляционном же исчислении формулировка этого запроса должна иметь следующий вид: { t.Назв_дет \t in r and t.Bec = 2}, где t – это переменная, обозначающая произвольную строку. Отношение, из которого берется t, определяется выражением "t in r", которое означает, что t – строка отношения. t.Haзв_дem – значение атрибута Назв_дет в строке t; символ (|) – разделяет целевой список и определяющее выражение. В данном случае: t.Haзв_дem – целевой список; t in r and t.Bec = 2 – определяющее выражение; t.Bec = 2 означает, что значение атрибута Вес в строке t равно 2. Фигурные скобки "{}", в которые заключено выражение, определяют результат запроса, как множество значений данных. Что именно входит в это множество, описывает выражение в скобках. Приведенное здесь решение иллюстрирует почти все элементы реляционного исчисления. Целевой список и определяющее выражение Решением каждого запроса в реляционном исчислении является отношение, которое задается целевым списком и определяющим выражением. Целевой список определяет атрибуты отношения решения. Определяющее выражение – это условие, на основании которого отбираются значения из базы данных, которые войдут в отношение решения. В предыдущем примере целевой список содержит только t.Haзв_дem, поэтому в данном случае отношение решения имеет только один атрибут. Легко понять, как операция выбора и проецирования реляционной алгебры поддерживаются в реляционном исчислении Действительные значения, входящие в отношение решения, берутся из тех строк, которые удовлетворяют определяющему выражению. В этом примере Назв_дет берется из строки t и помещается в строку решения, если строка t удовлетворяет условию t in r and t.Bec = 2. Система просматривает строки отношения r одну за другой. Первой строке временно присваивается имя t и проверяется истинность определяющего выражения. Поскольку в этом случае t.Bec = 1, определяющее выражение, ложно, поэтому A – значение атрибута t.Назв_дет в этой строке не помещается в отношение решения. Затем система переходит к следующей строке, дает ей имя t и снова проверяет истинность определяющего выражения. На этот раз выражение истинно, поэтому Д помещается в отношение решения. Процесс повторяется для каждой строки отношения r. В результате получается следующее отношение, идентичное полученному ранее:
Вообще говоря, целевой список может состоять из нескольких атрибутов. В списке можно перечислить даже все атрибуты, разделив их запятыми: {t.Koд_дem, t.Назв_дет, t.Bec \t inr and t.Bec = 2}. Более того, можно выбрать любое требуемое подмножество из этих атрибутов. Рассмотрим еще один пример. Пусть даны отношения:
Согласно алгебраическому выражению Рназв-е(t = ) реляционной алгебры, содержащему операции пересечения и проецирования, получим отношение:
В реляционном же исчислении, если t кортеж r, а у кортеж s, этот запрос может включать в себя следующие компоненты: t. Назв_дет – целевой список; / in r and у in s and t. Код_дет = у.Код_дет and t.Вес = у.Вес and t. Назв_дет = у.Назв_дет – определяющее выражение. В приведенном определяющем выражении для иллюстрации подробно перечислены все атрибуты обоих отношений. Однако следует отметить, что чаще всего в этом нет необходимости, так как реляционное исчисление располагает средствами для того, чтобы данное определяющее выражение могло быть записано более компактно. В только что рассмотренных примерах были использованы операции выбора, пересечения и проецирования реляционной алгебры. Аналогично можно получить конструкции реляционного исчисления, соответствующие ряду других операций: объединению, разности и произведению. Несколько иначе выглядят аналоги только двух операций реляционной алгебры – операций соединения и деления. Для построения аналогов этих операций требуются кванторы: квантор существования для соединения и квантор всеобщности для деления. | |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||