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


 

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

52502. Доказывание в арбитражном процессе 341.04 KB
  Институт судебных доказательств относится к числу важнейших в тех отраслях российского права, которые регламентируют порядки отправления правосудия по гражданским, арбитражным, уголовным делам. Данному институту в целом и его отдельным аспектам посвящено неисчислимое количество монографий, статей, комментариев, диссертаций. Это вполне объяснимо, поскольку правильное использование доказательств в судебной практике гарантирует установление объективной истины:
52503. Диференціація – умова успішного навчання 95.5 KB
  Виконувати диференційовані завдання систематично майже на кожному уроці уникаючи стандарту. Добирати завдання з поступовим ускладненням для сильніших і зменшувати міру допомоги для слабших учнів. Диференціацію бажано застосовувати під час фронтальної роботи коли учні розвязують загальні навчальні завдання. Добирати варіативні завдання що полегшують роботу вчителя і учнів в перевірці цих завдань.
52504. Практический материал для развития речевого дыхания при открытой ринолалии 75 KB
  Речевое дыхание характеризуется коротким вдохом и удлиненным выдохом. При проведении работы по нормолизации дыхания необходимо соблюдать ряд правил: заниматься только в проветренном помещении до еды; строго дозировать количество и темп упражнений при недомогании лучше отложить занятия не делать слишком большой вдох; следить чтобы ребенок не напрягал плечи шею; ребенок должен ощущать движения диафрагмы межреберные мышцы мышцы нижней части живота; движения необходимо производить плавно под счет тихо. Сделать полный...
52505. Значение дыхания. Строение и функции органов дыхания. Голосовой аппарат 378 KB
  Строение и функции органов дыхания. Разработка содержит: конспект урока с поэтапным описанием методов и форм работы учителя и учащихся продолжительностью этапов урока в виде таблицы и ожидаемыми результатами презентации: Строение органов дыхания Эрудицион созданы в PowerPoint видеофайл Строение органов дыхания формат МР4 аудиозапись отрывков из оперы Джузеппе Верди. Тема: Значение дыхания.
52506. Болезни органов дыхания. Профилактика. Вредное влияние курения, загрязнения окружающей среды 37.5 KB
  Взрослым и детям для предупреждения этой болезни делают прививки. Возбудитель попадает в организм воздушнокапельным путем может длительное время находиться в организме человека н вызывая болезни. Ее положительная реакция говорит о присутствии возбудители этой болезни в организме.
52507. Дихальні здоров’єзберігаючі технології на уроках читання 48 KB
  Технологія Стоніжка. Технологія Свічка. Технологія Проколотий мяч. Технологія Передай звуками для очищення легенів.
52508. ДИХАННЯ 262 KB
  9 КЛАС Цикл уроків з розділу Біологія людини у 9 класі на тему Дихання розроблено згідно з Програмою з біології для 7 11 класів загальноосвітніх навчальних закладів що затверджена Міністерством освіти і науки України 2005 року. Запропонована методична розробка уроків теми Дихання відповідає підручнику С. Планування навчального матеріалу з теми Дихання 6 годин № уроку Тема уроку 1.
52509. ТАЄМНИЦЯ РІЗДВА. УРОК-ЗУСТРІЧ З ГЕРОЯМИ ТВОРУ Ч.ДІККЕНСА «РІЗДВЯНА ПІСНЯ В ПРОЗІ» 80 KB
  The teacher: Charles Dickens, a famous British writer, also wrote about Christmas in his book Christmas Carol. He was born in 1812. He lived in the south of England when he was a little boy. His father was a clever man, but he was very poor. Charles had brothers and sisters, but he did not often played with them.