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


 

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

84519. Складно-рефлекторна (цефалічна) фаза регуляції шлункової секреції 42.2 KB
  Кількість та склад шлункового соку змінюється особливо після вживання їжі. В значній мірі кількість та склад соку залежить від характеру подразника кількість та склад їжі. Натще секретується невелика кількість шлункового соку до 10 мл на годину. Після прийому їжі виділення шлункового соку значно збільшується росте його кислотність та вміст ферментів.
84520. Нейро-гуморальна (шлункова і кишкова) фаза регуляції шлункової секреції. Ентеральні стимулятори і інґібітори шлункової секреції 43.73 KB
  Ентеральні стимулятори і інґібітори шлункової секреції. Хімічна стимуляція секреції здійснюється посередництвом гастрину що виділяється Gклітинами. Основні стимулятори секреції гастрину – продукти переварювання білків – пептиди олігопептиди амінокислоти – особливо триптофан і фенілаланін а також кальцій магній алклголь та кофеїн.
84521. Рухова функція шлунку та її регуляція. Механізми переходу хімуса із шлунку в дванадцятипалу кишку 41.86 KB
  Механізми переходу хімуса із шлунку в дванадцятипалу кишку. В регуляції моторики шлунку беруть участь нервові та гуморальні механізми. Деякі м’язові клітини внутрішнього шару м’язової оболонки шлунку мають пейсмейкерну активність тобто періодично генерують ПД – з частотою 32 на секунду що спричиняє періодичне підвищення внутрішньошлункового тиску.
84522. Методи дослідження зовнішньосекреторної функції підшлункової залози у людини. Склад і властивості підшлункового соку 44.04 KB
  Основні аніони підшлункового соку – Cl- та HCO3- , катіони – Na+ та K+. На відміну від слини, сік ізотонічний плазмі крові незалежно від ступеня стимуляції. Концентрація катіонів при стимуляції лишається сталою, аніонів – змінюється в протилежному напрямку. Карбонат утворюється в ацинусах у більш високій концентрації, а при проходженні через протоки частково обмінюється на хлор
84523. Фази регуляції секреторної функції підшлункової залози 44.07 KB
  Секреція підшлункового соку під час цієї фази пов’язана з реалізацією складнорефлекторних механізмів регуляції тобто умовних рефлексів вигляд запах їжі і з реалізацією безумовних рефлексів подразнення їжею рецепторів ротової порожнини.Об’єм соку невеликий 20 від загального об’єму соку який виділяється при їді; 3.Сік містить багато ферментів і має високу перетравлюючу силу. Він викликає виділення великої кількості підшлункового соку багатого бікарбонатами але бідного на ферменти так як основна його дія спрямована на протокові...
84524. Методи дослідження жовчовиділення у людини. Склад і властивості жовчі 48.34 KB
  Склад і властивості жовчі. Для збільшення надходження жовчі в дуоденум підшкірно можна вводити гормон ХЦКПЗ або через зонд – концентрований розчин MgSO2 яєчний жовток чи глюкозу які стимулюють секрецію та виділення жовчі. В жовчі досліджують вміст жовчних кислот та інших компонентів. Даний метод базується на тому що у випадку порушення функції виділення жовчі в крові та в сечі концентрація жовчних пігментів підвищується а в калі навпаки – понижується.
84525. Регуляція утворення і виділення жовчі. Механізми надходження жовчі в дванадцятипалу кишку 39.8 KB
  Механізми надходження жовчі в дванадцятипалу кишку. Механізм жовчоутворення та жовчовиділення: Утворення жовчі іде постійно але збільшується під час травлення під впливом складнорефлекторних механізмів які відносяться до 1ї фази жовчоутворення вигляд запах їжі звуки що супроводжують їду а також нейрогуморальних впливів які діють під час 2ї фази жовчоутворення та жовчовиділення. Механізм надходження жовчі в дванадцятипалу кишку: Вихід жовчі з жовчного міхура та її рух по жовчовивідних шляхах зумовлений різницею тисків в...
84526. Склад і властивості кишкового соку. Регуляція його секреції. Порожнинне і пристінкове травлення 42.9 KB
  Порожнинне і пристінкове травлення. Поняття про порожнинне та пристінкове травлення: Порожнинне травлення проходить в порожнині кишкового каналу за рахунок ферментів. Порожнинне травлення може забезпечити гідроліз до кінцевих продуктів але його тривалість дуже велика. Пристінкове травлення проходить на мембрані глікокалікса мікроворсинок ентероцитів за допомогою фіксованих ферментів активні центри яких направлені на субстрат.
84527. Всмоктування в травному каналі. Механізми всмоктування йонів натрію, води, вуглеводів, білків, жирів 44.89 KB
  Механізми всмоктування йонів натрію води вуглеводів білків жирів. Всмоктування – це процес транспорту речовин із порожнини травного каналу у внутрішні середовища організму кров та лімфу. Найінтенсивніше процеси всмоктування проходять в верхніх відділах тонкого кишківника. Всмоктування в шлунку.