17227

ЗАВИСИМЫЕ РЕЛЯЦИОННЫЕ ОПЕРАЦИИ

Лекция

Информатика, кибернетика и программирование

Лекция №6 Зависимые реляционные операции Как было сказано в начале главы не все операции реляционной алгебры являются независимыми некоторые из них выражаются через другие реляционные операции. Операция соединения Операция соединения определяется ч...

Русский

2013-06-30

87.5 KB

6 чел.

Лекция №6

Зависимые реляционные операции

Как было сказано в начале главы, не все операции реляционной алгебры являются независимыми - некоторые из них выражаются через другие реляционные операции.

Операция соединения

Операция соединения определяется через операции декартового произведения и выборки. Для операции естественного соединения добавляется операция проекции.

Операция пересечения

Операция пересечения выражается через вычитание следующим образом:

A EXCEPT B = A INTERSECT (A INTERSECT B)

Операция деления

Операция деления выражается через операции вычитания, декартового произведения и проекции следующим образом:

A / B = X(A) INTERSECT X((X(A) JOIN B) INTERSECT A)

или по-другому, разделив каждую операцию

T = A / B

T1 = X(A) 

T2 = X((T1 JOIN B) INTERSECT A)

T = T1 INTERSECT T2

Таким образом, показано, что операции соединения, пересечения и деления можно выразить через другие реляционные операции, т.е. эти операции не являются примитивными (тривиальными).

Примитивные (тривиальные) реляционные операторы

Рассмотренные операции объединение, вычитание, декартово произведение, выборка, проекция являются примитивными операторами, так как их нельзя выразить друг через друга.

Операция декартового произведения

Операция декартового произведения - это операция, увеличивающая количество атрибутов, поэтому ее нельзя выразить через объединение, вычитание, выборку, проекцию.

Операция проекции

Операция проекции - операция, уменьшающая количество атрибутов, поэтому ее также нельзя выразить через объединение, вычитание, декартово произведение, выборку.

Операция выборки

Операция выборки - операция, позволяющая проводить сравнения по атрибутам отношения, поэтому ее нельзя выразить через объединение, вычитание, декартово произведение, проекцию.

Операции объединения и вычитания

Доказательство примитивности операций объединения и вычитания более сложны и выражаются через другие теоретико-множественные операции.

Запросы, невыразимые средствами реляционной алгебры

Несмотря на мощность языка реляционной алгебры, имеется ряд типов запросов, которые принципиально нельзя выразить только при помощи операций реляционной алгебры. Это не означает, что ответы на эти запросы нельзя получить вообще. Просто, для получения ответов на подобные запросы приходится применять процедурные расширения реляционных языков.

Плохая нормализация отношений

Данный пример взят из книги [Гилуа М.М. Множественная модель данных в информационных системах. - М.: Наука, 1992, стр.43].

Пример. Пусть имеется отношение ХИМИЧЕСКИЙ СОСТАВ ВЕЩЕСТВ с набором атрибутов (Наименование вещества, Водород, Гелий, …, 105_элемент). Значениями атрибута " Наименование вещества" являются наименования химических веществ, значениями остальных атрибутов - процентный состав соответствующих элементов в этом веществе.

Такое отношение могло бы иметь, к примеру, следующий вид:

Таблица 24 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

Наименование вещества

Водород

Гелий

105 элемент

Дезоксирибонуклеиновая кислота

5

3

0.01

Бензин

50

0

0

Рассмотрим запрос "Найти все химические элементы, содержание которых в каком-либо из веществ превышает заданный процент (скажем, 90)".

С алгоритмической точки зрения этот запрос выполняется просто - просматриваются все столбцы таблицы, если в столбце присутствует хотя бы одно значение, большее 90, то запоминается заголовок этого столбца. Набор наименований запомненных столбцов и является ответом на запрос.

Формально невозможно выразить этот запрос в рамках реляционной алгебры, т.к. ответом на этот запрос должен быть список атрибутов отношения, удовлетворяющих определенному условию. В реляционной алгебре нет операторов, манипулирующих с наименованиями атрибутов.

На самом деле, этот пример показывает, что таблица плохо нормализована (нормализация отношений будет рассмотрено далее). В таблице есть набор однотипных атрибутов ("Водород", "Гелий" и т.д. в количестве 105 столбцов).

Правильнее разбить это отношение на три различных отношения:

  1.  ВЕЩЕСТВО (НОМ_ВЕЩЕСТВА, ВЕЩЕСТВО); 
  2.  ЭЛЕМЕНТЫ (НОМ_ЭЛЕМЕНТА, ЭЛЕМЕНТ); 
  3.  ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ (НОМ_ВЕЩЕСТВА, НОМ_ЭЛЕМЕНТА, ПРОЦЕНТ).

Таблица 25 Отношение ВЕЩЕСТВО

НОМ_ВЕЩЕСТВА

ВЕЩЕСТВО

1

Дезоксирибонуклеиновая кислота

2

Бензин

Таблица 26 Отношение ЭЛЕМЕНТЫ

НОМ_ЭЛЕМЕНТА

ЭЛЕМЕНТ

1

Водород

2

Гелий

105

Таблица 27 Отношение ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ

НОМ_ВЕЩЕСТВА

НОМ_ЭЛЕМЕНТА

ПРОЦЕНТ

1

1

5

1

2

3

1

105

0.01

2

1

50

Для отношений, нормализованных таким образом, исходный запрос реализуется следующей последовательностью операторов:

  1.  R1 = ПРОЦЕНТ>90(ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ) – (Выборка из отношения).
  2.  R2 = НОМ_ЭЛЕМЕНТА (R1) – (Проекция отношения).
  3.  R3 = НОМ_ЭЛЕМЕНТА, ЭЛЕМЕНТ(R2 JOIN ЭЛЕМЕНТЫ) – (Естественное соединение)
  4.  R4 = ЭЛЕМЕНТ(R3) – (Проекция таблицы).

На языке SQL такой запрос реализуется одной командой:

SELECT a.ЭЛЕМЕНТ

 FROM ЭЛЕМЕНТЫ as a, ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ as b

 WHERE a.НОМ_ЭЛЕМЕНТА = b.НОМ_ЭЛЕМЕНТА

 AND b.ПРОЦЕНТ>90

Невыразимость транзитивного замыкания реляционными операторами

Следующий пример иллюстрирует класс запросов, невыразимых средствами реляционной алгебры по причине невыразимости средствами реляционной алгебры транзитивного замыкания отношений.

Введем понятие транзитивного замыкания.

Определение. Пусть отношение  задано на декартовом квадрате  некоторого множества . Транзитивным замыканием отношения называется новое отношение , состоящее из кортежей , для которых выполняется:

  •  либо кортеж ,
  •  либо найдется конечная последовательность элементов , такая, что все кортежи принадлежат отношению .

Очевидно, что .

Смысл замыкания  состоит в описании включения значений друг в друга не только непосредственно, а через использование их в промежуточных значениях.

Пример. Рассмотрим отношение, описывающее сотрудников некоего предприятия СОТРУДНИКИ (ТАБ_НОМ, ФАМИЛИЯ, ДОЛЖНОСТЬ, ТАБ_НОМ_РУК):

Таблица 28 Отношение СОТРУДНИКИ

ТАБ_НОМ

ФАМИЛИЯ

ДОЛЖНОСТЬ

ТАБ_НОМ_РУК

1

Иванов

Директор

1

2

Петров

Глав.бухгалтер

1

3

Сидоров

Бухгалтер

2

4

Васильев

Начальник цеха

1

5

Сухов

Мастер

4

6

Шарипов

Рабочий

5

Рассмотрим запрос "Перечислить всех руководителей (прямых и непрямых) данного сотрудника".

Ответом на запрос может быть получен при помощи понятия транзитивного замыкания. Однако транзитивное замыкание не может быть выражено операторами реляционной алгебры.

Запросы такого рода называются рекурсивными, и могут быть сформулированы, если известны вся цепочка транзитивного замыкания.

Например, для рассмотренного примера, с учетом того, что отношение конечно запрос можно сформулировать как набор вложенных запросов на выборку. Хотя этот запрос также не решает задачу полностью (!). Для поиска начальника бухгалтера (‘Сидоров’, таб_ном = 3) необходимо запрос формулировать заново.

Пример запроса поиска начальника рабочего (‘Шарипов’, таб_ном = 6).

Select фамилия

From сотрудники

Where таб_ном =

(select таб_ном_рук

from сотрудники

where таб_ном =

(select таб_ном_рук

from сотрудники

where таб_ном =

(select таб_ном_рук

from сотрудники

where таб_ном = 6)))

Кросс – таблицы (перекрестные запросы)

Одной из задач, связанных с представлением табличных данных является построение так называемых кросс - таблиц.

Пусть имеется отношение с тремя атрибутами и потенциальным ключом, включающим первые два атрибута. Примером такого отношения могут быть данные с объемами продаж различных товаров за некоторые промежутки времени:

Таблица 29 Данные о продажах

Товар

Месяц

Количество

Компьютеры

Январь

100

Принтеры

Январь

200

Сканеры

Январь

300

Компьютеры

Февраль

150

Принтеры

Февраль

250

Сканеры

Февраль

350

Требуется представить эти данные в виде таблицы, по строкам которой идут наименования товаров, по столбцам - месяцы, а в ячейках содержатся объемы продаж. Это и будет кросс - таблицей:

Таблица 30 Кросс-таблица

Товар

Январь

Февраль

Компьютеры

100

150

Принтеры

200

250

Сканеры

300

350

Построение кросс - таблицы средствами реляционной алгебры невозможно, т.к. для этого требуется перевести данные из ячеек таблицы в наименования новых столбцов таблицы.

Такой результат можно достичь, используя перекрестный запрос. Такой запрос нельзя выразить одной инструкцией SQL. Если в функции СУБД входит реализация инструкции TRANSFORM (как, например, в Access), то запрос можно сформулировать следующим образом:

TRANSFORM Количество

SELECT Товар FROM Продажи GROUP BY Количество, Товар

PIVOT Месяц

Общий синтаксис перекрестного запроса:

TRANSFORM выражение с итоговой функцией – определяет значения, которые должны появиться в ячейках перекрестного запроса

SELECT инструкция, содержащая группировку GROUP BY для вычисления итоговой функции

PIVOT выражение – задает имена полей перекрестной таблицы

[ IN альтернативный список имен полей ]


 

А также другие работы, которые могут Вас заинтересовать

47143. The attribute. Ways of expressing attributes 66.5 KB
  The attribute is a secondary part of the sentence which characterizes person or non-person expressed by the headword either qualitatively, quantitatively, or from the point of view of situation. Attributes may refer to nouns and other words of nominal nature, such as pronouns gerunds and substitute words, as in...
47145. Определение числовой последовательности и её предела 66.64 KB
  предел функции одной переменной в точке.бесконечно большие и бесконечно малые функции. Предел функциис его помощью определяются многие др. Определение предела функции в точке по Коши число А принадлежащее R называется пределом функции fх в точке х0 если она определена в некоторой проколотой окрестности точки х0 и если для любого сколь угодно малого числа Е 0 можно указать такое число b=b х0 е 0 что для всех х удовлетворяющих условие 0 xx0 b выполняется неравенство fx e если e 0 b 0 то 0 xx0 b Определение предела функции в...
47147. Ответственность за экологический вред, принесенный источником повышенной опасности 67.18 KB
  Возмещение вреда причиненного источником повышенной опасности для окружающей среды характеризуется существенной спецификой. К объектам повышенной опасности ГК РФ относит средства механизмы электрическую энергию высокого напряжения атомную энергию взрывчатые вещества сильнодействующие яды и т. Обязанность возмещения такого вреда возлагается на юридическое лицо или гражданина которые владеют источником повышенной опасности на праве собственности праве хозяйственного ведения или праве оперативного управления либо на ином...
47148. Способи розпізнавання та класифікації помилок ТСП 67.5 KB
  Самые распространенные из них описываются ключевыми словами wire и reg соответственно. Однако следует помнить что средство синтеза не всегда реализует reg в виде триггера. Отличие wire от reg состоит в том что reg способен сохранять присвоенное значение работает как переменная в языках программирования а к wire требуется прилагать непрерывное воздействие driver. Существуют также wnd wor tri0 tri1 trind trior и trireg это цепь а не регистр для моделирования различных типов цепей wnd wired nd tri0 резистор к 0 trireg ...
47149. Международные системы стандартной нумерации изданий (ISBN, ISSN и пр.): сфера применения, состав, структура, расположение в издании и порядок присвоения. Штриховой код EAN 68 KB
  5301 Международная стандартная нумерация книг регламентирующих правила проставления международного стандартного номера книги Interntionl stndrd book number ISBN на книжные издания введенных в действие в январе 1988 г. ISBN позволяет издателям книготорговцам библиотекарям научным работникам признанным во всем мире способом беспрепятственно осуществлять распространение литературы в соответствии со спросом усовершенствовать поиск и заказ изданий весь цикл создания и доведения книги до потребителя. ISBN является обязательным...
47150. Организация как система 71.73 KB
  Xарактеристика организации как системы Организацией признается юридическое лицо которое имеет в собственности хозяйственном ведении или оперативном управлении обособленное имущество и отвечает по своим обязательствам этим имуществом может от своего имени приобретать и осуществлять имущественные и личные неимущественные права нести обязанности быть истцом и ответчиком в суде. Организации могут быть формальными и неформальными. Неформальные организации также представляют группы людей. Различают простые и сложные организации.