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


 

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

76540. Языковой разбор и его роль в формировании знаний, навыков и умений обучающихся 30 KB
  Языковой разбор и его роль в формировании знаний навыков и умений обучающихся. Языковый разбор представляет собою лингвистический анализ и толкование предложенного учителем дидактического материала: это могут быть отдельные слова предложения небольшие тексты. Языковый разбор основывается на рецептивной деятельности учащихся так как проводится на готовом языковом материале восприятие которого сквозь призму изученных понятий и правил и составляет суть метода. В зависимости от того какое умение отрабатывается различаются следующие виды...
76542. Методы практического изучения языка и обучения речи. Анализ текста на уроке русского языка 26.5 KB
  Анализ текста на уроке русского языка. Сочинение вид письменной школьной работы изложение своих мыслей знаний на заданную тему Анализ текста. анализ текста создаёт условия для формирования у школьников представления о языковой системе реализации внутрипредметных межуровневых а также метапредметных связей включает уроки русского языка в единую систему филологического образования. Определить тему и проблему текста 3.
76543. Урок как основная форма обучения. Основные свойства и структура урока 32.5 KB
  Урок как основная форма обучения. Основные свойства и структура урока. Классификация: урок объяснение новых знаний введение новых теоретических понятий уроки закрепления формирования умений и навыков урок повторения и обобщения урок контролирования или контрольный урок. комбинированный урок классический Классификация в соответствии с ведущим методом обучения: урок лекция урок семинар урок практикум урок зачетТак же выделяются уроки развития речи2 направления: развитие речи на уроке с любой темой то есть изучение грамматики и...
76545. Методика изучения раздела «фонетика, графика, орфоэпия». Цели, содержание, методы обучения 31 KB
  Необходимо при изучении словообразования: буквы имеющие два один звук. Цель изучения: осознаное усвоение звуковой системы языка; знакомство с орфоэпическими нормами СРЛЯ; формирование орфографических навыков.Задачи:Формирование основных фонетических понятий: звук слог ударение интонация; ать представление о русской графике как науке устанавливающей общие принципы передачи звучащей речи на письме; Развивать фонематический слух учащегося и на этой основе формировать орфографическую грамотность школьника; Закрепить умение обозначить звуки...
76546. Методика обучения лексике и фразеологии. Цели, содержание, методы обучения 34 KB
  Цель формирование представлений о лексико фразеологической системе русского языка; знакомство со лексическим и нормами русского литературного языка; обогащение словарного запаса учащихся; Задачи: формирование основных лексических понятий знакомство с разными способами пополнения словарного запаса научить школьников определять роль лексических и фразеологических единиц речи сформировать умение школьников использовать лексику и фразеологизмы в соответствии с лексич значением научить пользоваться разными видами словарей В начальной школе...
76547. Обзор лингвистических терминов по морфемике и словообразованию 27.5 KB
  Морфема служит для образования новых слов или форм слова и может воспроизводиться в составе слова. Выделить в составе слова его значимые части то есть морфемы корень приставка суффикс окончание В 56 классах школьники знакомится с морфемой и словообр системой как с элементами системы языка. На первых же уроках по изучению морфемики учащиеся учатся различать два понятия словообразование и словоизменение Корень слова основная морфема в которой заключено основное лексическое значение слова. Окончание флексия значимая часть слова изменяемая...