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 альтернативный список имен полей ]


 

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

19912. Естественные источники радиации 59.5 KB
  PAGE 6 Тема 4. Естественные источники радиации Вопросы: 1.Космические лучи 2.Земная радиация 3.Внутреннее облучение 4.Радон 5.Другие источники радиации Вступление Основную часть облучения население земного шара получает от естественн
19913. Искусственные источники радиации 63 KB
  Тема 5. Искусственные источники радиации Вопросы: 1.Источники использующиеся в медицине 2.Ядерные взрывы 3.Атомная энергетика 4.Прфессиональное облучение 5.Другие источники облучения Вступление За последние полвека человек созда...
19914. Биологическое действие ионизирующих излучений 372 KB
  PAGE 21 Тема 6. Биологическое действие ионизирующих излучений Вопросы: 1.Этапы действия ионизирующих излучений. Механизм биологического действия и.и. 2.Действие доз радиации 3.Радионуклиды и растительный мир 4.Влияние радионуклидов на животн...
19915. ПРИНЦИПЫ И КРИТЕРИИ РАДИАЦИОННОЙ БЕЗОПАСНОСТИ (Радиационная гигиена) 291.5 KB
  Тема 7. ПРИНЦИПЫ И КРИТЕРИИ РАДИАЦИОННОЙ БЕЗОПАСНОСТИ Радиационная гигиена Вопросы: 1.Нормы радиационной безопасности НРБ2000. 2.Республиканские допустимые уровни содержания р.н. в продуктах питания. 3.Способы защиты человека от радиаци
19916. Авария на Чернобыльской АЭС и ее последствия для Республики Беларусь 84.5 KB
  Тема 8. Авария на Чернобыльской АЭС и ее последствия для Республики Беларусь Вопросы: 1.Принцип работы ядерного реактора 2.Авария на ЧАЭС и ее причины. 3.Последствия аварии на ЧАЭС для Республики Беларусь 8.1. Принцип работы ядерного реа
19917. Радиационная безопасность 7.84 MB
  МЕТОДИЧЕСКИЕ УКАЗАНИЯ к лабораторным работам по курсу €œРадиационная безопасность€ для студентов всех специальностей дневной формы обучения. Статистическая обработка результатов имеет две основные задачи. Определение плотности потока бета-излучения с поверхности. Определение мощности экспозиционной и эквивалентной доз прибором «РД-1503»...
19918. Вводная лекция. Предмет экономики предприятия 19.99 KB
  Тема: Вводная лекция. Предмет экономики предприятия. Вопросы по лекции: Экономика предприятия как самостоятельная экономическая дисциплина. Эволюция развития и функции теории управления предприятия. Объект изучения экономики предприятия. Миссия и цели
19919. Технологический процесс 22.39 KB
  Лекция №2 Тема: Технологический процесс Технологический процесс это совокупность действий по изменению и определению состояния. Производственные процессы различают по различным признакам: По назначению Основные Вспомогательные Обслуживающие
19920. Хозяйственные ресурсы предприятия. Основные фонды предприятия 21.47 KB
  Лекция №3 Тема: Хозяйственные ресурсы предприятия. Основные фонды предприятия. План: Понятия производственных ресурсов Экономическая сущность состав классификация и структура основных фондов ОФ. Экономическая оценка ОЦ ОФ. Износ ОФ Амортизация ...