Базы данных

Конспект лекций | назад | содержание | вперед

Раздел 4. Реляционная алгебра и реляционное исчисление Работники отдела информационных систем фирмы, обсуждают отличия языков реляционных баз данных.Когда Кодд впервые ввел реляционную модель данных, он предложил процедурный язык, реляционную алгебру, непроцедурный язык и реляционное исчисление.— Что означает процедурный и непроцедурный7— В непроцедурном языке мы сообщаем компьютеру, что нужно сделать. В процедурном языке мы сообщаем компьютеру, как нужно выполнять каждый шаг. Традиционные компьютерные языки являются процедурными. Реляционная модель привела к развитию на практике непроцедурных языков.— Создается впечатление, что непроцедурные языки являются языками более высокого уровня, чем процедурные. Тогда почему бы не моделировать все реляционные языки на основе реляционного исчисления?— Наиболее популярные языки следуют этой тенденции. Однако, реляционная алгебра обладает некоторыми определенными преимуществами, и некоторые языки, например, языки систем R:base, основаны на ней. Для того чтобы хорошо понимать реляционную модель и языки, используемые для работы с ней, важно полностью разобраться в обоих подходах. В этой главе представлено подробное введение в реляционную алгебру и реляционное исчисление, на которых базируются коммерческие языки, используемые в реляционных базах данных. Познакомившись с этими двумя языками, вы сможете в дальнейшем изучать и использовать любой из множества языков баз данных, основанных на них. Прочитав эту главу, вы должны уметь: Перечислить операции реляционной алгебры и показать, как пользоваться ими для создания новых реляционных таблиц из уже существующих. Продемонстрировать структуру запросов в реляционном исчислении, особенно условные утверждения, которые нужно формулировать для реализации запроса. Сформулировать конкретные типы запросов на обоих языках. Тема 4.1. Революционный подход к обработке данных В 1970-1971 годах Е.Ф.Кодд опубликовал две статьи, в которых ввел реляционную модель данных и реляционные языки обработки данных -реляционную алгебру и реляционное исчисление. Хотя реляционная модель сама по себе имела важное значение, именно реляционные языки оказались серьезным основанием для реляционной революции в базах данных. В конце концов, реляционная модель, в которой данные представлены в виде таблиц, очень похожа на существовавшие до нее файлово-ориентированные модели. По общему признанию, изменения терминологии — реляционная таблица вместо файла, атрибут вместо поля и т.д. — имели важное значение, поскольку они подчеркивали логический смысл данных, а не их физическую структуру. Однако, по прошествии времени оказалось, что наиболее важным аспектом новой модели были ее конкретные языки данных, которые позволили манипулировать данными на основе только их логических характеристик. В этой главе мы будем изучать два предложенных Коддом языка, реляционную алгебру и реляционное исчисление. В первой статье Кодд предложил реляционную модель данных и реляционную алгебру. Реляционная алгебра — это процедурный язык обработки реляционных таблиц. Это означает, что в реляционной алгебре используется пошаговый подход к созданию реляционных таблиц, содержащих ответы на запросы. В последующих статьях Кодд ввел реляционное исчисление. Реляционное исчисление — непроцедурный язык. В реляционном исчислении запрос создается путем определения таблицы запроса за один шаг. Реляционная алгебра . Процедурный язык обработки реляционных таблиц. Процедурный язык . Язык, обеспечивающий пошаговое решение задач. Реляционное исчисление . Непроцедурный язык создания запросов. Непроцедурный язык . Язык, позволяющий формулировать, что нужно сделать, а не как этого добиться. Кодд показал, что реляционная алгебра и реляционное исчисление логически эквивалентны, что чрезвычайно важно. Это означает, что любой запрос, который можно сформулировать при помощи логического исчисления, также можно сформулировать, пользуясь реляционной алгеброй, и наоборот. Этот факт позволил измерять логическую мощность языка запросов. Если язык имеет как минимум те же возможности, что и реляционная алгебра, то он называется реляционно полным. Это означает, что любой запрос, который можно сформулировать в реляционной алгебре, должен формулироваться в “реляционно полном языке”. Таким образом, при создании коммерческих реляционных языков можно тестировать их логические возможности путем сравнения с реляционной алгеброй или реляционным исчислением. Если язык имеет меньшую логическую мощность, чем реляционная алгебра или исчисление, то наверняка существуют запросы, которые нельзя формулировать с помощью этого языка. Реляционно полный язык. Язык, имеющий такую же логическую мощность, что и реляционная алгебра и реляционное исчисление.Реляционная алгебра также имеет важное значение, так как из нее происходят многие термины для понятий обработки данных, часто встречающиеся в коммерческих языках баз данных. Такие термины, как выбирать, проектировать, соединять или объединительно-совместимый, происходят из реляционной алгебры. Кроме того, некоторые коммерческие языки баз данных основаны на реляционной алгебре.Реляционное исчисление имеет важное значение по двум причинам: Оно основано на исчислении предикатов формальной логики, которое является эффективным методом определения истинности высказывания на основе истинности его компонентов. Следовательно, реляционное исчисление имеет столь же твердую логическую основу, что и любой существующий язык программирования. Несколько коммерческих реляционных языков концептуально близки к нему. Мы изучим некоторые из этих языков в дальнейших главах. И реляционная алгебра, и реляционное исчисление в том виде, как они были сформулированы Коддом и как они обсуждаются в этой главе, являются теоретическими языками. Таким образом, мы интересуемся только логическими аспектами алгебры и исчисления, а не конкретными их реализациями. Следовательно, мы будем весьма свободно и неформально подходить к определению и использованию синтаксиса. Если бы мы занимались конкретными коммерческими языками — такими, как рассматриваемые в дальнейших главах — нам пришлось бы соблюдать большую точность. На протяжении главы мы будем пользоваться для иллюстраций базой данных, приведенной на рис. 4.1. Эта база данных взята из примера компании International Product Distribution (Глава 1). Тема 4.2. Реляционная алгебра Операции реляционной алгебры манипулируют реляционными таблицами, то есть эти операции используют одну или две из существующих таблиц для создания новой таблицы. Затем полученная новая таблица может использоваться в качестве входной для новой операции. Эта важная идея — создание новых таблиц на основе старых — делает возможным необозримое множество обработки данных. Она также чрезвычайно упрощает создание запросов, поскольку мы можем экспериментировать с частичными решениями, пока не найдем работающий способ решения. Реляционная алгебра состоит из следующих девяти операций: объединения, пересечения, разности, произведения, выбора, создания проекций, соединения, деления и присвоения. Первые четыре операции взяты из математической теории множеств и практически совпадают с операциями теории множеств. Это разумно, поскольку реляционные таблицы являются множествами, так что вполне естественно, что к ним применимы операции над множествами. Следующие четыре — новые операции, относящиеся только к реляционной модели данных. Последняя операция — присвоение — стандартная операция компьютерного языка, дающая имя величине. В нашем случае производится присвоение имени новой таблице, созданной из существующих таблиц. Мы будем пользоваться для обозначения присвоения имен таблицам знаком :=. Мы обсудим операции в том порядке, в котором они были перечислены. 4.2.1. Объединение Операция объединения (U) позволяет нам комбинировать данные из двух таблиц. Пример. Пусть отношения А и В будут такими, как показано на рисунке. Отношение А представляет поставщиков из Москвы, а отношение В — поставщиков, которые, например, поставляют деталь Р1. A
S# | SNAME | STATUS | CITY
S1 | БАЙТ | 20 | Москва
S4 | ЛОТОС | 20 | Москва
B
S# | SNAME | STATUS | CITY
S1 | БАЙТ | 20 | Москва
S2 | БИТ | 10 | Новосибирск
С := A UNION B
S# | SNAME | STATUS | CITY
S1 | БАЙТ | 20 | Москва
S4 | ЛОТОС | 20 | Москва
S2 | БИТ | 10 | Новосибирск
Рис.4.1. Операция ОБЪЕДИНЕНИЕ Тогда выражение C:=A UNION B представляет поставщиков, которые или размещаются в Москве, или поставляют деталь Р1 (либо и то и другое). Обратите внимание, что результат имеет три кортежа, а не четыре — повторяющиеся кортежи удаляются по определению. Объединение . Операция реляционной алгебры, создающая теоретико-множественное объединение двух объединительно-совместимых реляционных таблиц. C — это имя, присвоенное полученной в результате реляционной таблице, состоящей из тех строк, которые лежат либо в таблице А, либо в В, либо в них обеих. Важно отметить, что любая строка, существующая в обеих таблицах, появляется в таблице объединения только один раз. Это следует из определения реляционной таблицы как множества, поскольку данное свойство встречается в множестве только один раз. Мы должны указать специальное требование к операции объединения, которое слегка отличает ее от обычного объединения множеств в математике. В математике можно объединить любые два множества. Но в реляционной алгебре, прежде чем применять операцию объединения к двум реляционным таблицам, необходимо убедиться, что они имеют в точности одни и те же столбцы, то есть у них совпадает как количество столбцов, так и области столбцов. Если это условие выполнено, то таблицы называются объединительно-совместимыми. Очевидно, таблицы А и В объединительно-совместимы. Объединительно-совместимые таблицы . Две или более реляционные таблицы, имеющие эквивалентные столбцы (с точки зрения их количества и областей). Объединительная совместимость требуется для того, чтобы результатом выполнения операции объединения была реляционная таблица. Если мы объединим, например, таблицы КЛИЕНТ и ТОВАР, то мы получим множество, но не реляционную таблицу. Значения в строках полученного в результате множества не будут соответствовать одним и тем же столбцам, так что их нельзя будет организовать в реляционную таблицу. Таким образом, ясно, что объединительная совместимость необходима для операции объединения. По тем же причинам она необходима для операций пересечения и разности. 4.2.2. Пересечение Пересечение . Операция реляционной алгебры, создающая пересечение в теоретико-множественном смысле двух объединительно-совместимых реляционных таблиц. Операция пересечения ( INTERSECT) позволяет нам идентифицировать строки, общие для двух таблиц. Пример . Пусть снова отношения А и В будут такими, как показано на рисунке. Тогда выражение D := A INTERSECT B представляет поставщиков, которые размещаются в Москве и поставляют деталь Р1. D := A INTERSECT B
S# | SNAME | STATUS | CITY
S1 | БАЙТ | 20 | Москва
Рис.4.2. Операция ПЕРЕСЕЧЕНИЕ Результатом выполнения операции пересечения будет реляционная таблица, состоящая из всех строк, встречающихся в обеих исходных таблицах. То есть, если D — пересечение А и В, то С состоит из тех строк, которые есть и в А, и в В. Как и ранее, А и В должны быть объединительно-совместимы. 4.2.3. Разность Разность . Операция реляционной алгебры, создающая теоретико-множественную разность двух объединительно-совместимых реляционных таблиц. Операция разности (обозначаемая знаком MINUS) позволяет идентифицировать те строки, которые есть в одной таблице, но отсутствуют в другой. Пример . Пусть снова отношения А и В будут такими, как показано на рисунке. Тогда выражение E := A MINUS B представляет поставщиков, которые размещаются в Москве и не поставляют деталь Р1, а В MINUS А представляют поставщиков, которые поставляют деталь Р1 и не размещаются в Москве. E := A MINUS B
S# | SNAME | STATUS | CITY
S4 | ЛОТОС | 10 | Москва
G := B MINUS A
S# | SNAME | STATUS | CITY
S2 | БИТ | 20 | Новосибирск
Рис.4.3. Операция ВЫЧИТАНИЕ Разность двух реляционных таблиц определяется как таблица, состоящая из всех строк, входящих в первую таблицу, но не входящих во вторую. То есть, если E := А MINUS В то строками E являются те строки, которые есть в А, но которые отсутствуют в В. Обратите внимание, что А MINUS В не совпадает с В MINUS А Таким образом, порядок таблиц в операции разности очень важен. Отметим, что таблицы должны быть объединительно-совместимыми. Операцию разности можно также назвать операцией вычитания. Эта операция имеет большое значение при решении некоторых сложных задач, которые без нее были бы неразрешимы. 4.2.4. Произведение Произведение . Операция реляционной алгебры, создающая декартово произведение двух реляционных таблиц. Операция произведения, обозначаемая символом *, имеет большое значение в качестве составной части операции соединения, которая, вероятно, является наиболее важной операцией в реляционной алгебре. Она идентична математической операции взятия декартова произведения двух множеств. Сейчас мы поясним, что это значит, на простом абстрактном примере. Рассмотрим реляционные таблицы на рис. 4.4(а). А и В — две реляционные таблицы, каждая из которых состоит из двух столбцов. А и В имеют атрибуты Х,Y и W,Z соответственно. Рис.4.4а. Реляционные таблицы А и В Произведением таблиц А и В будет таблица С, представленная на рис. 4.4б. С := А * В Рис.4.4б. Произведение А и В Обратите внимание, что произведение создано путем Связывания, или соединения, атрибутов двух таблиц; Присоединения к каждой строке таблицы А каждой строки таблицы В. Таким образом, атрибутами С будут все атрибуты А и В вместе взятые. Поскольку таблицы А и В имеют по два атрибута каждая, то С будет иметь четыре атрибута. Строки С созданы соединением строк А и В. Каждая строка А спарена с каждой строкой В. Таким образом, поскольку в В три строки, каждая строка А связывается с тремя строками В и повторяется в строках С три раза. Легко видеть, что число строк С всегда будет равно произведению числа строк А на число строк В. Пример 2. Предположим, мы хотим взять произведение таблиц ТОВАР и ПРОДАЖА. П_П := ТОВАР * ПРОДАЖА П_П будет состоять из 10 столбцов и 40 строк. В этом случае возникает небольшая проблема, поскольку столбец таблицы ТОВАР и столбец таблицы ПРОДАЖА (КОД_ТОВАРА) имеют одно и то же имя. Эта проблема преодолевается путем добавления к имени столбца имени исходной таблицы. Таким образом, в П_П у нас будут столбцы ТОВАР.КОД_ТОВАРА и ПРОДАЖА.КОД_ТОВАРА. Никакие очевидные применения операции произведения в голову не приходят; неясно, какого типа запросы могут создаваться при помощи взятия произведения двух реляционных таблиц. Но как мы увидим, произведение применяется как составная часть операции соединения. Следовательно, она важна в концептуальном плане; далее в этой главе мы приведем достаточное количество примеров. Операция произведения также используется в языке запросов SQL, который является наиболее важным коммерческим реляционным языком. 4.2.5. Выборка Выборка. Операция реляционной алгебры, производящая отбор строк из таблицы на основании некоторого условия.Замечание. Нижеследующие примеры данной главы в качестве исходных таблиц используют таблицы, представленные на рис. 4.5. Операция выборки используется для создания реляционной таблицы из другой реляционной таблицы путем отбора только тех строк, которые удовлетворяют заданному условию. Например, рассмотрим такой запрос: Запрос : Выдать всю информацию о торговых агентах в Токио. На этот запрос можно ответить, выбрав из таблицы ТОРГОВЫЙ_АГЕНТ (рис. 4.5) строки на основании следующего условия: строка выбирается только в том случае, если значение атрибута ОФИС равно “Токио”. В реляционной алгебре это делается следующим образом: SP := SELECT (ТОРГОВЫЙ_АГЕНТ : ОФИС = ‘Токио’) Имя SP создано нами для обозначения таблицы. Ключевое слово SELECT используется для обозначения производимой операции выбора. За словом SELECT мы помещаем в скобках имя таблицы, из которой выбираются строки, затем двоеточие и условие выбора. Строки, удовлетворяющие условию, будут выбраны и помещены в результирующую таблицу. Результатом выполнения этой операции выбора будет следующая таблица: SP
КОД_ АГЕНТА | ИМЯ_ АГЕНТА | КОД_ МЕНЕДЖЕРА | ОФИС | ПРОЦЕНТ
14 | Масаи | 44 | Токио | 11
39 | Ацума | 44 | Токио | 10
44 | Волков | 27 | Токио | 12
Условия выбора в основном такие же, как и условия, используемые в IF выражениях традиционных языков программирования. Однако, необходимо следить, чтобы имена столбцов, используемые в условиях выбора, обязательно встречались в таблице, из которой производится выбор. Ниже приведены некоторые примеры условий выбора, которые могут использоваться с таблицей ТОРГОВЫЙ_АГЕНТ: КОД_АГЕНТА = 23 ИМЯ_АГЕНТА = ‘Волков’ КОД_МЕНЕДЖЕРА >= 44 ОФИС NOT= ‘Чикаго’ Обратите внимание, что мы можем пользоваться операторами сравнения, такими, как “<” и “>”. Таких операторов сравнения пять: ==, <, >, <=, >=. Для каждого из них есть соответствующий оператор, использующий булеву операцию “не”. Так, у нас есть “=” и “не=”, так же, как и “<” и “не<”. и т.д. Мы также можем использовать булевы операторы “и” и “или”. “Не” также можно использовать в общем случае для отрицания всего условия. Эти понятия мы поясним следующими примерами: Примеры: Запрос : Какой торговый агент имеет код 23? Решение : SELECT (ТОРГОВЫЙ_АГЕНТ : КОД_АГЕНТА = 23) Запрос : Выдать всю информацию об агенте Волков Решение : SELECT (ТОРГОВЫЙ_АГЕНТ : ИМЯ_АГЕНТА = ‘Волков’) Запрос : Кто из торговых агентов работает с менеджером, код которого больше или равен 20? Решение : SELECT (ТОРГОВЫЙ_АГЕНТ : КОД_МЕНЕДЖЕРА >= 20) Запрос : Выдать информацию обо всех тоговых агентах, кроме тех, котторые работают в Токио. Решение : SELECT (ТОРГОВЫЙ_АГЕНТ : ОФИС NOT= ‘Токио’) Запрос : Кто из торговых агентов в Токио получает более 10% комиссионных?. Решение : SELECT (ТОРГОВЫЙ_АГЕНТ : ОФИС = ‘Токио’ AND ПРОЦЕНТ > 10) Запрос : Кто из торговых агентов отчитывается перед менеджером 27 или получает более 10% комиссионных?. Решение : SELECT (ТОРГОВЫЙ_АГЕНТ : КОД_МЕНЕДЖЕРА = 27 OR ПРОЦЕНТ > 10) 4.2.6. Создание проекций Некоторые из запросов, приведенных для иллюстрации операции выборки формулировались “Кто...”, то есть предполагалось, что пользователям требовались только имена торговых агентов, удовлетворяющих условию запроса. При этом ответ на каждый запрос содержал полные строки данных, взятые из таблицы ТОРГОВЫЙ_АГЕНТ, поскольку операция выбора всегда извлекает строки целиком. Очевидно, что нам требуется некоторый способ исключения ненужных столбцов. Если операцию выборки можно представить себе как исключение ненужных строк, то операцию создания проекций можно представить как исключение ненужных столбцов. Полученная в результате операции создания проекций таблица называется проекцией исходной таблицы. Создание проекций . Операция реляционной алгебры, создающая новую таблицу путем исключения столбцов из существующей таблицы. Проекция . Реляционная таблица, полученная в результате создания проекций.В отличие от других операций реляционной алгебры, операция создания проекций не требует специального ключевого слова или символа. Вместо этого для того чтобы создать проекцию — реляционную таблицу, состоящую только из некоторых определенных столбцов другой реляционной таблицы — мы просто указываем исходную таблицу, а после нее в квадратных скобках перечисляем те столбцы, которые мы хотим оставить. Например, если мы хотим идентифицировать торговых агентов в Токио, мы можем взять проекцию столбца имени таблицы SP. SP [ИМЯ_АГЕНТА] В результате мы получим следующую реляционную таблицу:
ИМЯ_ АГЕНТА
Масаи
Ацума
Волков
Мы могли бы выбрать более одного столбца. Так, если бы нам был нужен код, имя и менеджер каждого из этих агентов, мы должны ввести: SP [КОД_АГЕНТА, ИМЯ_АГЕНТА, КОД_МЕНЕДЖЕРА] В результате мы получим следующую реляционную таблицу:
КОД_ АГЕНТА | ИМЯ_ АГЕНТА | КОД_ МЕНЕДЖЕРА
14 | Масаи | 44
39 | Ацума | 44
44 | Волков | 27
Предположим, что нас интересуют разные проценты комиссионных, выплачиваемые торговым агентам. Мы можем получить их просто проекцией на столбец ПРОЦЕНТ таблицы ТОРГОВЫЙ_АГЕНТ: SP [ПРОЦЕНТ] В результате мы получим следующую реляционную таблицу:
ПРОЦЕНТ
10
11
9
13
15
12
Обратите внимание, что каждая ставка комиссионных встречается только один раз, несмотря на то, что несколько разных агентов получают одинаковые комиссионные. Поскольку реляционная таблица — множество, каждая данная ставка не повторяется. Это важная характеристика операции создания проекций. Она автоматически исключает повторы из результирующей таблицы. Это происходит и в том случае, когда результирующая таблица содержит более одного столбца. Если две строки таблицы содержат идентичные значения в каждом столбце проекции, то строка войдет в результирующую таблицу только один раз. Операция создания проекций — удобный повод показать вложение операций в реляционной алгебре. Под вложением мы подразумеваем последовательное выполнение операций без явного присвоения имени промежуточной таблице результатов. Например, добавим операцию создания проекций к одному из запросов, иллюстрирующих операцию выбора. Запрос : Кто из торговых агентов получает менее 11% комиссионных? Решение: SELECT (ТОРГОВЫЙ_АГЕНТ: ПРОЦЕНТ < 10) [ИМЯ_АГЕНТА] В этом примере сначала выполняется операция выбора, а затем результаты проектируются на столбец ИМЯ_АГЕНТА. Вложение операций можно производить произвольным образом, при необходимости используя скобки для определения порядка операций. 4.2.7. Соединение Соединение . Операция реляционной алгебры, связывающая таблицы. Операция соединения используется для связывания данных между таблицами. Это, возможно, наиболее важная функция любого языка баз данных. У нее есть несколько версий: естественное соединение, тета-соединение и внешнее соединение. Наиболее важным из них является естественное соединение. 4.2.7.1. Естественное соединение Рассмотрим таблицу ПРОДАЖА (рис. 4.5). В нее записываются идентификаторы клиента, торгового агента и товара, участвующих в каждой продаже. Эта информация позволяет нам создать логические связи с таблицами КЛИЕНТ, ТОРГОВЫЙ_АГЕНТ и ТОВАР. Предположим, что мы хотим знать названия фирм-клиентов, которые производили закупки через торгового агента 10. Сначала мы выберем продажи, относящиеся к торговому агенту 10, и поместим их в таблицу, которую назовем ПРОДАЖА_10. В результате мы получим следующую таблицу: ПРОДАЖА_10
ДАТА | КОД_ КЛИЕНТА | КОД_ АГЕНТА | КОД_ ТОВАРА | КОЛИЧЕСТВО
08.02 | 100 | 10 | 2241 | 200
24.02 | 105 | 10 | 2241 | 100
1.03 | 105 | 10 | 2249 | 50
Теперь мы можем получить нужные данные путем соединения таблиц ПРОДАЖА_10 и КЛИЕНТ. Эта операция выполняется следующим образом: Создается произведение таблиц КЛИЕНТ и ПРОДАЖА_10. В результате получается таблица, содержащая 11 столбцов (5 из таблицы ПРОДАЖА_10, 6 из таблицы КЛИЕНТ) и 12 строк (3 таблицы ПРОДАЖА_10 * 4 таблицы КЛИЕНТ). Из таблицы произведения исключаются все строки кроме тех, в которых КОД_КЛИЕНТА из таблицы ПРОДАЖА_10 равен КОД_КЛИЕНТА из таблицы КЛИЕНТ. Результат представлен на рис. 4.6. Обратите внимание, что в полученной таблице два столбца КОД_КЛИЕНТА, и в каждой строке значения этих двух столбцов совпадают. Поскольку столбцы КОД_КЛИЕНТА содержат одинаковую информацию, один из них можно удалить. В результате получится естественное соединение таблиц ПРОДАЖА_10 и КЛИЕНТ, представленное на рис. 4.7. Естественное соединение . Операция соединения, связывающая таблицы, когда общие столбцы имеют равные значения Разумеется, мы получили гораздо более подробную информацию, чем просто названия фирм-клиентов. Если бы мы хотели получить только названия, мы могли бы выполнить проекцию на столбец ИМЯ_КЛИЕНТА таблицы на рис. 4.7. Возможно, проще понять, что происходит при соединении таблиц, рассматривая процесс с точки зрения табличного поиска. Для каждой строки реляционной таблицы ПРОДАЖА_10 мы ищем строки в таблице КЛИЕНТ, имеющие такое же значение КОД_КЛИЕНТА. Поскольку КОД_КЛИЕНТА является ключом таблицы КЛИЕНТ и поскольку в нашей базе данных поддерживается целостность на уровне ссылок, такая строка всегда будет ровно одна. Таким образом, поскольку в таблице ПРОДАЖА_10 три строки, присоединив таблицу КЛИЕНТ к таблице ПРОДАЖА_10, мы получим таблицу, состоящую также из трех строк. Мы просто расширили каждую строку таблицы ПРОДАЖА_10, добавив к ней информацию о клиенте, участвующем в продаже. Операция естественного соединения в этом примере записывается следующим образом: JOIN (ПРОДАЖА_10, КЛИЕНТ) Общее определение естественного соединения таково: Предположим, что мы хотим взять естественное соединение двух таблиц А и В, имеющих общие столбцы С1,...,Сn. Тогда операция JOIN (А, В) выполняется за следующие три шага: 1. Берется произведение таблиц А и В. В результате получается таблица, содержащая по два столбца на каждый С1,...,Сn. 2. Из таблицы произведения исключаются все строки кроме тех, в которых значения столбцов С1,...,Сn из таблицы А равны соответственно, значениям этих столбцов в В. 3. Проектированием исключается одна копия столбцов С1,...,Сn. В большинстве наших примеров две таблицы, соединение которых выполняется, будут иметь только один общий столбец. Однако, как показывает общее определение, если две реляционные таблицы имеют более одного общего столбца, то соединение производится на основании равенства значений во всех общих столбцах. Мы подчеркиваем, что если таблица А имеет k столбцов, а таблица В имеет m столбцов, то естественное соединение таблиц А и В будет состоять из (k+m-n) столбцов, где n — число общих столбцов таблиц А и В. Теперь мы проиллюстрируем использование и возможности соединения при помощи нескольких примеров запросов. Запрос : Присоединить информацию о продажах к информации о торговых агентах. Решение : JOIN (ТОРГОВЫЙ_АГЕНТ, ПРОДАЖА) Результат: на рис.4.8. Это в точности тот же самый запрос, что и в предыдущем примере, за исключением того, что мы воспользовались таблицей ТОРГОВЫЙ_АГЕНТ вместо таблицы КЛИЕНТ. Мы привели этот пример, чтобы проиллюстрировать другой взгляд на соединение. В этом случае запрос начинается с того, что мы смотгрим на таблицу ТОРГОВЫЙ_АГЕНТ и говорим, что информацию о продажах нужно присоединить к строкам этой таблицы. Поскольку разные торговые агенты могут участвовать более чем в одной продаже или же ни в одной продаже, мы видим, что некоторые строки с одним и тем же агентом повторяются несколько раз, тогда как строки с другими агентами отсутствуют вовсе. Многие считают, что в этом случае что-то теряется, поскольку торговые агенты, для которых нет продаж в базе данных, отсутствуют в результирующей таблице естественного соединения. Для решения этой проблемы было предложено внешнее соединение, которое обсуждается далее в этой главе. Запрос : Выдать название фирмы-клиента, участвующей в каждой продаже. Решение : A := КЛИЕНТ(КОД_КЛИЕНТА, ИМЯ_КЛИЕНТА) B := JOIN ( ПРОДАЖА, А) Результат: на рис.4.9. В этом примере, прежде чем выполнять соединение, созданием проекции удалили ненужную информацию из таблицы КЛИЕНТ. Ответ на запрос находится в таблице, которую мы назвали В. Обратите внимание, что столбец КОД_КЛИЕНТА таблицы ПРОДАЖА был сочтен избыточным и удален. Запрос : Выдать список клиентов, закупивших товар 2518. Решение : A := SELECT (ПРОДАЖА: КОД_ТОВАРА = 2518) B := JOIN ( А, КЛИЕНТ) [ИМЯ_КЛИЕНТА] Результат: ниже. В
ИМЯ_ КЛИЕНТА
Смит
Мальтц
Гомес
В данном примере сначала создается уменьшенная таблица продаж А, в которой находятся только товары с кодом 2518. Затем эта таблица соединяется с таблицей КЛИЕНТ, после чего проектирование оставляет только столбец ИМЯ_КЛИЕНТА, записывая результаты в таблицу В. Операцию выбора можно выполнять второй, а не первой. В этом случае решение будет выглядеть так: A := JOIN ( ПРОДАЖА, КЛИЕНТ) B := SELECT (А: КОД_ТОВАРА = 2518) [ИМЯ_КЛИЕНТА] Это решение логически эквивалентно первому, то есть оба решения дают один и тот же результат. Однако, первое решение более предпочтительно, поскольку оно будет выполняться быстрее. Это следует из того, что таблица А в первом решении значительно меньше, чем таблица ПРОДАЖА. В результате для выполнения соединения требуется произвести значительно меньше сравнений. Как правило, более эффективно выполнять операции типа соединения, требующие большого количества сравнений, после операций, уменьшающих количество строк, подвергаемых сравнению, таких как выбор. Разумеется, это возможно только в том случае, когда существует более одного логически правильного решения. Запрос : Кто покупал настольные лампы? Решение : A := SELECT (ТОВАР: ОПИСАНИЕ = ‘Настольная лампа’) B := JOIN ( А, ПРОДАЖА) [ИМЯ_КЛИЕНТА] С := JOIN ( В, КЛИЕНТ) [ИМЯ_КЛИЕНТА] Результат: ниже. С
ИМЯ_ КЛИЕНТА
Смит
Мальтц
Джексон
В этом примере мы должны следовать логическим путем от “настольных ламп” таблицы ТОВАР к атрибуту ИМЯ_КЛИЕНТА таблицы КЛИЕНТ. Для того чтобы сделать это, мы идентифицируем все товары — настольные лампы, а затем переходим от таблицы ТОВАР к таблице ПРОДАЖА, а затем к таблице КЛИЕНТ. Мы делаем это посредством двух операций соединения. Поскольку нас интересует только название клиента, мы на последнем шаге проектированием исключаем все остальные столбцы. Запрос : Кто из агентов продавал товары, произведенные в Перу? Решение : A := SELECT (ПРОИЗВОДИТЕЛЬ: СТРАНА = ‘Перу’) B := JOIN ( А, ТОВАР) С := JOIN ( В, ПРОДАЖА) D := JOIN ( C, ТОРГОВЫЙ_АГЕНТ) [ИМЯ_АГЕНТА] Результат: ниже. D
ИМЯ_ АГЕНТА
Джонс
Муар
Этот запрос аналогичен предыдущему, только путь от страны изготовителя к агенту на одну таблицу длиннее. Таким образом, мы должны выполнить три операции соединения и связать четыре таблицы. Одна из промежуточных таблиц будет содержать 16 столбцов, но поскольку нас интересуют только атрибуты СТРАНА и ИМЯ_АГЕНТА, мы можем игнорировать все остальные атрибуты. Последняя таблица D, однако, содержит только один столбец, как показано выше. 4.2.7.2. Тета-соединение Рассмотрм следующий запрос: Запрос : Идентифицировать агентов, чьи менеджеры получают комиссионные более 11%. Все данные, нужные для решения, находятся в таблице ТОРГОВЫЙ_АГЕНТ, поскольку в ней содержатся данные обо всех торговых агентах — и о менеджерах, и о тех, которые менеджерами не являются. Однако на этот запрос нельзя ответить простой операцией выбора, так как размер комиссионных в записи о торговом агенте относится к торговому агенту, а не к его менеджеру. Для того чтобы выяснить размер комиссионных менеджера, мы должны присоединить запись о менеджере из таблицы ТОРГОВЫЙ_АГЕНТ к записи о торговом агенте. Таким образом, мы должны соединить таблицу ТОРГОВЫЙ_АГЕНТ с ней самой. Тогда размер комиссионных менеджера будет стоять в той же строке, что и имя торгового агента, и мы сможем легко завершить запрос. Например, первая строка таблицы ТОРГОВЫЙ_АГЕНТ содержит информацию о Джонсе. Как вы видите, код его менеджера равен 27. Это КОД_АГЕНТА Кардон, то есть он является менеджером Джонса. Поскольку размер ее комиссионных равен 15%, менеджер Джонса получает более 11 процентов комиссионных, и Джонс должен быть включен в результаты запроса. Присоединив таблицу ТОРГОВЫЙ_АГЕНТ к ней самой, мы можем добавить запись о менеджере к записи о каждом агенте и затем применить команду выбора к полученной таблице, чтобы ответить на запрос. Но как соединить таблицу с ней самой? Мы не можем воспользоваться естественным соединением, поскольку оно будет производиться на основании равенства всех общих столбцов соединяемых таблиц. Если таблицы в операции соединения совпадают, то у них общими являются все столбцы, и соединение бессмысленно. Мы решаем эту проблему путем определения нового типа соединения. Этот тип соединения позволяет нам задавать условие соединения строк. Следующее решение иллюстрирует этот новый тип соединения. Сначала создаются две копии таблицы ТОРГОВЫЙ_АГЕНТ. SP1 := ТОРГОВЫЙ_АГЕНТ SP2 := ТОРГОВЫЙ_АГЕНТ A := JOIN ( SP1, SP2: SP1.КОД_МЕНЕДЖЕРА = SP2.КОД_АГЕНТА) Последнее выражение является образцом новой версии соединения. Условие, следующее за двоеточием, означает, что две строки должны соединяться, если КОД_МЕНЕДЖЕРА первой строки равен КОД_АГЕНТА второй строки. Другими словами, мы присоединяем к каждой строке агента строку, содержащую информацию о его менеджере. Это показано на рис. 4.10. Обратите внимание, что в результирующей таблице отсутствует строка, показывающая Кардон и ее менеджера. Это происходит потому, что Кардон, не имеющий менеджера, имеет пустое значение в столбце КОД_МЕНЕДЖЕРА. Однако она выведена в качестве менеджера в строках нескольких других агентов. Мы еще не закончили этот запрос. Мы все еще должны идентифицировать тех торговых агентов, чьи менеджеры получают комиссионные более 11%. Мы можем завершить запрос простой операцией выбора, примененной к таблице А: В := SELECT (А: SP2.ПРОЦЕНТ > 11) [SP1.ИМЯ_АГЕНТА] Мы получим следующий результат:
SP1.ИМЯ_ АГЕНТА
Джонс
Масаи
Ацума
Волков
Карлсон
Филиппов
Обратите внимание, что нам нужен столбец SP2.ПРОЦЕНТ и не нужен SP1.ПРОЦЕНТ. Первый из них содержит размер комиссионных менеджера, тогда как последний содержит размер комиссионных агента. Тета-соединение — это соединение с определенным условием, в котором участвуют столбцы из каждой таблицы. Это условие означает, что два столбца будут определенным образом сравниваться. Оператор сравнения может быть любой из шести следующих: =, не =, <,>, <=, >= Тета-соединение. Операция соединения, связывающая таблицы, когда значения из определенных столбцов находятся в определенном отношении. Общий вид тета-соединения таков: JOIN (А, В: Х Θ У) где А и В — соединяемые таблицы, Х и У — столбцы из этих двух таблиц, а греческая буква Θ обозначает один из шести операторов, перечисленных выше. Наш пример иллюстрирует тета-соединение в случае, когда оператор сравнения “=”. Такое соединение также называется эквисоединением. В некоторых задачах требуются другие операторы. Мы приведем один такой пример далее в этой главе. Эквисоединение . Тета-соединение,. основанное на равенстве определенных столбцов. В качестве последнего замечания скажем, что тета-соединение, в отличии от естественного соединения, не включает удаление одного или более столбцов на последнем шаге. Другими словами, если таблица А содержит k столбцов, а таблица В — m столбцов, то тета-соединение А и В будет состоять из k+m столбцов. 4.2.7.3. Внешнее соединение Рассмотрим снова запрос, который обсуждался выше. Запрос : Присоединить информацию о продажах к информации о торговых агентах. JOIN (ТОРГОВЫЙ_АГЕНТ, ПРОДАЖА) Результаты выполнения этого запроса представлены на рис. 4.8. Однако этот результат неудовлетворителен, так как целью запроса является перечисление всех торговых агентов вместе с их продажами. Если мы пользуемся естественным соединением, то строки тех агентов, которые не производили продаж, не показаны. Таким образом, мы не можем пользоваться естественным соединением, если наряду с агентами, участвовавшими в продажах, мы хотим перечислять агентов, не производивших продаж. Внешнее соединение расширяет естественное соединение, гарантируя, что каждая запись из обеих исходных таблиц будет представлена в таблице соединения хотя бы один раз. Внешнее соединение выполняется в два этапа. Сначала выполняется естественное соединение. Затем, если какая-либо строка одной из исходных таблиц не подходит ни к какой строке второй таблицы, она включается в таблицу соединения, а все дополнительные столбцы заполняются пустыми значениями. Для предыдущей задачи это показано на рис. 4.11. Эта таблица — результат выполнения следующей операции. OUTJOIN (ТОРГОВЫЙ_АГЕНТ, ПРОДАЖА) Внешнее соединение . Расширение естественного соединения, включающее все строки из обеих таблиц. Некоторые версии SQL, например, Oracle, дают возможность внешнего соединения. Хотя потребность в нем невелика, мы видим, что в некоторых случаях оно весьма желательно. 4.2.8. Деление Предположим, что у нас есть такой запрос: Запрос : Перечислить торговых агентов с указанием проданных товаров. Наш образец базы данных содержит четыре разных товара с кодами 1035, 2241, 2249 и 2518. Торговый агент удовлетворяет условиям запроса, если он продавал каждый из этих товаров хотя бы один раз. Другими словами для каждого из этих товаров в таблице ПРОДАЖА должна быть хотя бы одна строка, содержащая КОД_АГЕНТА этого агента. Подобный запрос можно осуществить с помощью операции деления. Деление . Операция реляционной алгебры, создающая новую таблицу путем выбора строк одной таблицы, соответствующих каждой строке другой таблицы. Центральное слово в этом запросе — каждый, поскольку требуется, чтобы для каждого торгового агента мы проверяли строки таблицы ПРОДАЖА до тех пор, пока не убедимся, что этот агент продавал каждый товар. Это требование отличается от всех описанных выше, так как до сих пор для выполнения операции мы могли работать с одной или двумя строками одновременно. Операция деления требует, чтобы мы рассматривали всю таблицу сразу. Как выполнить такой запрос? Мы будем следовать процедуре, близкой к той, которой мы воспользовались бы интуитивно, и покажем, как операция деления соотносится с этой процедурой. Очевидно, что если мы хотим знать, продавал ли торговый агент каждый товар, мы сначала должны получить таблицу, где каждый товар перечислен. Это таблица ТОВАР. Однако в других таблицах товар идентифицируется только по ключевому столбцу, а не по всей строке таблицы ТОВАР. Таким образом, ключ заменяет сам товар. Наш первый шаг состоит в том, что мы создаем таблицу, состоящую из значений ключевого атрибута для каждого товара в базе данных. Мы делаем это проектированием таблицы ТОВАР на столбец КОД_ПРОДУКТА: P1 := ТОВАР (КОД_ТОВАРА) Итак, Р1 — таблица, состоящая из всех значений КОД_ТОВАРА. Затем мы должны получить таблицу, содержащую все элементы, в которых торговый агент и товар стоят в одной продаже. Это, очевидно, делается проектированием таблицы ПРОДАЖА на КОД_ТОВАРА и КОД_АГЕНТА: Р1_S1 := ПРОДАЖА [КОД_ТОВАРА, КОД_АГЕНТА] Элементы таблицы Р1_S1 состоят из КОД_ТОВАРА и КОД_АГЕНТА и означают, что товар, представленный КОД_ТОВАРА, продавался агентом, представленным КОД_АГЕНТА. Таким образом, Р1_S1 состоит из всех сочетаний товар/агент, где данный агент продавал данный товар. Результат этих двух проектировании будет следующим: Теперь нам просто остается определить, кто из агентов представлен в таблице Р1_S1 в сочетании с каждым товаром. Это делается автоматически при помощи операции деления: A := P1_S1 / P1 В результате мы получим:
КОД_ АГЕНТА
23
Возможно, все это выглядит шаманством. Однако ничего подобного, поскольку результат просто соответствует определению операции деления в реляционной алгебре. Мы даем общее описание операции следующим образом. Допустим, что А, В и С — реляционные таблицы, и мы хотим разделить В на С и получить в результате А. Столбцы С должны составлять подмножество множества столбцов В. Столбцами А будут только те столбцы В, которые не являются столбцами С. Обратите внимание, что это соответствует предыдущему примеру. Столбцы Р1_S1 — КОД_ТОВАРА и КОД_АГЕНТА, а столбец Р1 — КОД_ТОВАРА; при этом столбец А — КОД_АГЕНТА. Строка помещается в таблицу А в том и только том случае, если она входит в В с каждой строкой С. Это также соответствует нашему примеру, так как единственная строка А (в которой КОД_АГЕНТА=23) входит в Р1_S1 с каждой строкой Р1, и это единственный КОД_АГЕНТА, входящий в Р1_S1 таким образом. Операция деления является обратной к операции произведения. Легко проверить, что если таблица является произведением двух таблиц В и С, то мы можем получить таблицу В, разделив произведение на С. То есть (В * С) / С = В Это объясняет, по аналогии с обычной арифметикой, почему операция деления так называется. Кодд включил ее в реляционную алгебру, чтобы обеспечить возможности, аналогичные квантору всеобщности реляционного исчисления. Мы обсудим это позже. На практике операция деления нужна для того чтобы мы могли выполнять запросы, содержащие в условии слона “все” или “каждый”. В примере, который мы только что обсуждали, условие гласило: Перечислить торговых агентов, которые продавали каждый товар. Как мы видели, операция деления существенно использовалась в решении. 4.2.9. Присвоение Присвоение . Операция реляционной алгебры, дающая имя таблице. Мы пользовались операцией присвоения на протяжении всей главы, давая имена таблицам. Например, в выражении А := SELECT (ТОРГОВЫЙ_АГЕНТ: ПРОЦЕНТ > 11) имя А было присвоено результату операции выбора. Символ “:==” означает “имя, присвоенное ...”. 4.2.10. Дополнительный пример Реляционная алгебра является замечательным эффективным и гибким языком, при помощи которого можно решать широкий спектр задач. В этом разделе мы приведем пример задачи, которую можно решить при помощи реляционной алгебры, хотя с первого взгляда это кажется не слишком просто. Решение требует творческого подхода к использованию операций реляционной алгебры. Запрос . Каков максимальный размер комиссионных? Бросающаяся в глаза трудность состоит в том, что у нас вроде бы нет способа сравнить все значения в столбце размера комиссионных, чтобы выяснить, какое из них максимально. Нам требуется сравнивать значения в разных строках, так что операция выбора нам не поможет, поскольку она обрабатывает за один раз одну строку. Однако тета-соединение сравнивает по крайней мере две строки. Мы воспользуемся им для того чтобы связать таблицу с ней самой: A := ТОРГОВЫЙ_АГЕНТ (ПРОЦЕНТ) B := A C := JOIN (A, B: A.ПРОЦЕНТ > B.ПРОЦЕНТ) В результате соединения мы получим следующую таблицу
А.ПРОЦЕНТ | В.ПРОЦЕНТ
10 | 9
11 | 10
11 | 9
13 | 10
13 | 11
13 | 9
13 | 12
15 | 10
15 | 11
15 | 9
15 | 12
15 | 13
12 | 10
12 | 11
12 | 9
Как воспользоваться этой таблицей для решения задачи? Если мы рассмотрим столбцы по отдельности, мы обнаружим важный факт. Левый столбец А.ПРОЦЕНТ содержит все величины комиссионных, кроме минимальной, а правый столбец В.ПРОЦЕНТ содержит все варианты комиссионных, кроме максимального. Теперь мы видим, как решить задачу. Вычтя множество комиссионных правого столбца из множества всех величин комиссионных, мы получим максимальный размер комиссионных, что и требовалось: D := C [B.ПРОЦЕНТ] E := A - D Таблица D — это правый столбец таблицы С, и поэтому она содержит все величины комиссионных, кроме максимальной, а А содержит все величины комиссионных. Их разность, Е, содержит только максимальный размер комиссионных и потому является ответом на запрос. Читателю должно быть ясно, что для того чтобы получить минимальный размер комиссионных, нужно в определении таблицы D подставить вместо столбца В.ПРОЦЕНТ столбец А.ПРОЦЕНТ. В остальном решение будет таким же. Решение этой задачи содержало два “трюка”: (1) тета-соединение таблицы с ней самой и (2) вычитание таблицы, содержащей все значения, кроме того, которое ищется, из множества всех возможных значений. Второй момент очень важен и часто необходим для выполнения более сложных запросов в реляционной алгебре. Тема 4.3. Реляционное исчисление В реляционном исчислении используется совершенно иной подход, чем в реляционной алгебре. Тем не менее, эти два языка логически эквивалентны. Это означает, что любой запрос, который можно выполнить на одном языке, можно выполнить и на другом. Реляционное исчисление мы опишем более кратко, поскольку сам язык имеет меньше конструкций. Запрос : Кто из торговых агентов работает в Токио? В реляционном исчислении этот запрос выполняется следующим образом: {r.ИМЯ_АГЕНТА : r IN ТОРГОВЫЙ_АГЕНТ AND r.ОФИС = ‘Токио’} Фигурные скобки {}, в которые заключено выражение, означают, что ответом на запрос будет множество значений данных. Что именно входит в это множество, описывает выражение в скобках. Приведенное здесь решение иллюстрирует почти все элементы реляционного исчисления. Мы перечислим части нашего решения и объясним их значение: r - это переменная, обозначающая произвольную строку. Таблица, из которой берется г, определяется выражением “r IN ТОРГОВЫЙ_АГЕНТ”, которое означает, что г — строка таблицы ТОРГОВЫЙ_АГЕНТ. Мы будем использовать для обозначения строк маленькие буквы латинского алфавита: r, s, р, q. r. ИМЯ_АГЕНТА — значение атрибута ИМЯ_АГЕНТА в строке г. Двоеточие (:) разделяет целевой список и определяющее выражение. Целевой список в данном случае r. ИМЯ_АГЕНТА а определяющее выражение r IN ТОРГОВЫЙ_АГЕНТ AND r.ОФИС = ‘Токио’ Мы кратко объясним смысл. Двоеточие можно читать как “такое, что”. r IN ТОРГОВЫЙ_АГЕНТ объясняется в п.1 r.ОФИС = ‘Токио’ означает, что значение атрибута ОФИС в строке r равно 'Токио'. 4.3.1. Целевой список и определяющее выражение Целевой список . Список в выражении реляционного исчисления, определяющий атрибуты таблицы решения. Определяющее выражение . Условие в выражении реляционного исчисления, ограничивающее вхождение элементов в таблицу решения. Решением каждого запроса в реляционном исчислении является реляционная таблица, которая задается целевым списком и определяющим выражением. Целевой список определяет атрибуты таблицы решения. Определяющее выражение — это условие, на основании которого отбираются значения из базы данных, которые войдут в таблицу решения. Сейчас мы объясним, как они работают. В предыдущем примере целевым списком был r. ИМЯ_АГЕНТА. Иными словами, таблица решения имеет только один атрибут, имя торгового агента. Действительные значения, входящие в таблицу решения, взяты из строк, которые удовлетворяют определяющему выражению. В этом примере имя агента берется из строки г и помещается в строку решения, если строка г удовлетворяет условию r IN ТОРГОВЫЙ_АГЕНТ AND r.ОФИС = ‘Токио’ Система просматривает строки таблицы ТОРГОВЫЙ_АГЕНТ, представленной на рис. 4.5, одну за другой. Первой строке временно присваивается имя r и проверяется истинность определяющего выражения. В этом случае, поскольку r.ОФИС = 'Чикаго', определяющее выражение, ложно, поэтому r.ИМЯ_АГЕНТА (Джонс) не помещается в таблицу решения. Затем система переходит к следующей строке, дает ей имя r и снова проверяет истинность определяющего выражения. На этот раз выражение истинно, поэтому Масаи помещается в таблицу решения. Процесс повторяется для каждой строки таблицы ТОРГОВЫЙ_АГЕНТ. В результате получается следующая таблица:
ИМЯ_ АГЕНТА
Масаи
Ацума
Волков
Для большинства запросов целевой список будет состоять из одного атрибута. Однако, вообще говоря, целевой список может состоять из нескольких атрибутов. Мы могли бы перечислить нужные атрибуты, разделив их запятыми: {r.КОД_АГЕНТА, r.ИМЯ_АГЕНТА, r.ИМЯ_ОФИС: r IN ТОРГОВЫЙ_АГЕНТ AND r.ОФИС = ‘Токио’} Пока из нашего объяснения легко понять, как операции выбора и проектирования реляционной алгебры поддерживаются в реляционном исчислении. Объединение, пересечение, разность и произведение также можно легко вывести из конструкций реляционного исчисления, которые мы обсудили к настоящему моменту. Поскольку в исчислении не используются пошаговые процедуры алгебры, операция присвоения не нужна. Таким образом, остались две операции реляционной алгебры, для которых мы пока не продемонстрировали аналог в реляционном исчислении — это операции соединения и деления. Для них требуются кванторы: квантор существования для соединения и квантор всеобщности для деления. 4.3.2. Квантор существования Квантор существования . Выражение реляционного исчисления, означающее существование хотя бы одной строки, удовлетворяющей условию. Квантор обозначает количество чего-либо. Квантор существования означает, что существует хотя бы один экземпляр определенного типа вещей. В реляционном исчислении квантор существования используется для задания условия того, что определенный тип строк в таблице существует. Рассмотрим пример, поясняющий это понятие: Запрос : Перечислить названия фирм-клиентов, покупавших товар 2518. Очевидно, что решением этой задачи будет таблица, содержащая названия некоторых клиентов. Это таблица, состоящая из одного столбца, так что целевым списком является r.ИМЯ_КЛИЕНТА где r — строка из таблицы КЛИЕНТ. Итак, у нас есть целевой список, но как быть с определяющим выражением? Для того чтобы клиент вошел в таблицу решения, он должен удовлетворять условию, что он закупал товар 2518. Другими словами, если код клиента встречается в строке таблицы ПРОДАЖА с КОД_ТОВАРА=2518, то этот клиент должен быть включен в решение. Таким образом, условие таково: существует хотя бы одна строка таблицы ПРОДАЖА, содержащая код клиента и КОД_ТОВАРА=2518. Это формулируется следующим образом: exists s IN ПРОДАЖА (s.КОД_КЛИЕНТА = r.КОД_КЛИЕНТА AND s.КОД_ТОВАРА=2518 ) Такое выражение читается: “Существует строка s в таблице ПРОДАЖА такая, что s.КОД_КЛИЕНТА = r.КОД_КЛИЕНТА и s.КОД_ТОВАРА=2518. (Слово существует образует квантор существования.) Обратите внимание, что это выражение определяет строку r. Если оно истинно, то есть для строки г существует такая строка s, то r.ИМЯ_КЛИЕНТА помещается в таблицу решения. Если выражение ложно — то есть такой строки s не существует — тогда r.ИМЯ_КЛИЕНТА не помещается в таблицу решения. Полное решение в реляционном исчислении выглядит так: (r. ИМЯ_КЛИЕНТА := r IN КЛИЕНТ AND exists s IN ПРОДАЖА (s.КОД_КЛИЕНТА = r.КОД_КЛИЕНТА AND s.КОД_ТОВАРА=2518) Оно описывает таблицу, состоящую из одного столбца и содержащую названия клиентов, взятые из строк таблицы КЛИЕНТ. Данное название помещается в таблицу решения, если его строка (r) удовлетворяет условию после двоеточия. Рассмотрим несколько строк таблицы КЛИЕНТ, чтобы понять, как будет применяться условие. Рассмотрим рис. 4.12. Первая строка таблицы КЛИЕНТ (которую мы означили r) имеет КОД_КЛИЕНТА = 100. ИМЯ_КЛИЕНТА (Смит) будет помещено в таблицу решения, если в таблице ПРОДАЖА существует строка, в которой КОД_КЛИЕНТА=100, а КОД_ТОВАРА=2518. Такая строка действительно существует, и мы обозначили ее s. Итак, г удовлетворяет определяющему условию, поэтому r.ИМЯ_КЛИЕНТА помещается в таблицу решения. Мы повторяем этот процесс для каждой строки таблицы КЛИЕНТ. Когда вторая строка обозначена г, мы должны найти соответствующую s в таблице ПРОДАЖА. В этом случае соответствующая s — это вторая строка таблицы ПРОДАЖА. Таким образом, Мальтц помещается в решение. Продолжая дальше, мы выясним, что клиент 105 (Джексон) не будет помещен в решение, а клиент 110 (Гомес) будет помещен в решение. Множество решения будет выглядеть так:
ИМЯ_ КЛИЕНТА
Смит
Мальтц
Гомес
В реляционной алгебре для выполнения этого запроса требуется соединение. Таким образом, мы показали, как квантор существования используется в реляционном исчислении для, того чтобы выполнять функцию соединения. В качестве последнего примера рассмотрим более сложный запрос, требующий двух соединений. Запрос : Кто покупал настольные лампы? Этот запрос использовался для иллюстрации соединения при описании реляционной алгебры. Решение в реляционном исчислении выглядит так: (r.ИМЯ_КЛИЕНТА. : г IN КЛИЕНТ and there exists s IN ПРОДАЖА and exist t IN ТОВАР) (s.КОД_КЛИЕНТА = r.КОД_КЛИЕНТА and s.КОД_ТОВАРА = t. КОД_ТОВАРА and t.ОПИСАНИЕ = 'Настольная лампа') 4.3.3. Квантор всеобщности Квантор всеобщности . Выражение реляционного исчисления, обозначающее, что некоторое условие применяется к каждой строке определенного типа. Квантор всеобщности означает, что некоторое условие применяется ко всем или к каждой строке некоторого типа. Он используется в тех же целях, что и операция деления реляционной алгебры. Мы проиллюстрируем его применение тем же запросом, который рассматривался в разделе об операции деления. Используем рис.4.13 для рассмотрения квантора существования, применив его к таблицам КЛИЕНТ, ПРОДАЖА и ТОВАР. Обратите внимание, что условие выбора торгового агента содержит слово каждый. В таблицу решения включаются только те агенты, которые продавали каждый товар. Если вы взглянете на полученный результат, то увидите, что условию запроса удовлетворяет только один торговый агент. Решение в реляционном исчислении таково: (r.ИМЯ_КЛИЕНТА. : г IN КЛИЕНТ and there exists p B ТОВАР exist s IN ПРОДАЖА) (r.КОД_АГЕНТА = s.КОД_АГЕНТА and s.КОД_ТОВАРА = p.КОД_ТОВАРА) Результат выполнения запроса:
ИМЯ_ АГЕНТА
Муар
На рис.4.14. показан квантор всеобщности, примененный к таблицам ТОРГОВЫЙ_АГЕНТ, ТОВАР и ПРОДАЖА. Имя торгового агента из строки r таблицы ПРОДАЖА помещается в таблицу решения, если определяющее выражение истинно для строки r. Рис.4.14 показывает, что определяющее выражение истинно, если r — строка, содержащая данные о Муаре. Для каждой строки р таблицы ТОВАР должна существовать строка s в таблице ПРОДАЖА, удовлетворяющая условию. Рисунок показывает, что соответствие между строками таблицы ТОВАР и строками таблицы ПРОДАЖА удовлетворяет условию, то есть s(1) соответствует р(1) s(2) соответствует р(2) s(3) соответствует р(3) s(4) соответствует р(4) В каждой из этих строк таблицы ПРОДАЖА КОД_АГЕНТА принадлежит Муару (23) и каждая из четырех строк продаж соответствует одному из четырех возможных товаров. Таким образом, Муар продавал каждый товар. Вопросы для самопроверки 1. В чем отличие реляционной алгебры от реляционного исчисления? 2. Какая операция реляционной алгебры позволяет объединять таблицы? 3. В чем отличие таких операций реляционной алгебры, как разность и пересечение? 4. Как выполняется операция декартово произведение? 5. Для чего используется операция проекции? 6. Какие виды соединения таблиц вы знаете? 7. Чем тета-соединение отличается от естетсвенного соединения? 8. Для чего служит целевой список в реляционном исчислении? 9. Для решения каких задач используется квантор существования? 10. Какие логические операторы можно использовать в операции выборки?

назад | содержание | вперед