Реляционная алгебра

Реляционная алгебра http://citforum.ru/database/dblearn/dblearn04.shtml

http://eos.ibi.spb.ru/umk/5_8/5/5_R0_T2.html

О1 отнош.Пусть даны N мн=в D1,D2, …. Dn (домены), отн R над этими мн-вами наз мн-во упоряд N-кортежей вида , где d1 принад D1 и тд. Мн-ва D1,D2,..Dn наз доменами отн R. Кажд эл кортежа предст зн одного из атриб, соотв одному из доменов. Любое отн имеет простую графич интерпре: оно м б изобр с пом табл: стцами таб явл атрибуты, а строками n-ки, кот в реляц модели наз кортежами

В отн треб, что все кортежи д различ Для однозн идент кортежа сущ 1ичн ключ. 1ичн ключ это атриб или набор из мин числа атриб, кот однозн идент конкр кортеж и не содерж доп атриб. Подраз, что все атриб в 1ичн ключе д б необх и дост для идент конкр кортежа, и искл люб из атриб в ключе сдел его недостат для идентификации.

Оп над 1 отнош наз унарными, над 2 отн — бинарными, над 3 — тернарными (таков практ неизв).

При унарной оп — проекция, прим бинарной операции — объед.

N-арную реляц оп f м предст функц, возвр отн и имеющ n отн в кач арг

Поск реляц алг явл замкн, в кач операнд в реляц оп м подст др выр реляц алг (подх по типу):

В реляц выр м испо влож выр ск угодно сложной структуры.

Реляционной базой данных наз с-ть отн, содерж всю информ, кот д хранится в базе.

Реляц алгебра предст набор таких оп над отнош, что рез кажд из оп также явл отнош. Это свойство алгебры наз замкнутостью.Для форм описания реляц алг вв мн-во симв:

• реляционных операций ={, , \, , , _B(r),  _rel(r), ^add, del, ch}.

• арифм опер ={=, , , , }, логических оп ={,,},

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

• -объед 2 отнош; - пересеч 2 отношений;

\-разность двух отнош;  -прямое произв двух отношений; -дополн отношения;

_B(r) -выбор кортежей из отн по усл, где _B(r) – усл выбора;

 _rel(r) -проекция отн на новую схему, где _rel(r) –новая схема отнош;

^--соед 2 отнош, где  - усл арифм сравн зн атрибутов;

: -деление одного отн на другое;

add-вставка кортежа в отн; del-удаление кортежа из отношения;

ch -изменение значений атрибутов кортежа отношения.

При зад парам мн-в R и REL(R) и зад мн-вах оп ;  и  реляц алгебра есть:

A=A; D; REL(R); R; ; ; . Эл мн-ва {_B(r), _rel(r), r, add(r), del(r), ch(r)} предст унар оп для преобр одного отн, а эл мн-ва {(r₁, r₂), (r₁, r₂), \(r₁, r₂), (r₁, r₂), r₁, r₂), ^r₁, r₂)), :(r₁,r₂)} – бинарные операторы для формир одного отн из двух заданных

мы описыв нашу обл знаний набором предикатов. Напр, "Поставщик нах в городе и имеет статус ", "Деталь наз и цвета ", "Поставщ поставл деталь в кол штук". Соотв, когда мы подст в предикат кортеж, получ высказ — ист или ложное. С каждым предикат ест связ мн-во (мн-во истинности), сост из всех кортежей, кот при подст в предикат дают истин высказ, и только из них. Это мн-во явл отнош, в мат см (в реляц теории, правда, принято опред отн и кортежи чуть иначе, чем в матем: комп-ты не нумер, а именуют). Ну вот, и мы хран в БД эти отно. Рассм предикат "Поставщик нах в городе , имеет статус и пост деталь в кол шт". Как найти его мн-во истинн? Возьмем мн-ва истинн предикатов и и сдел оп . И все ост реляц опер соотв каким-то логич оп с предикат. Если н что-то узнать, мы форм запрос в терм предикатов, соотв хранящ в БД отнош, автом переводим его в выр реляц алгебры — и высчит по имеющ отн мн-во истинн интерес нас запроса.

Ограничения на операции

Нек реляц оп, в частн, оп объединения, пересеч и вычит, треб, чтобы отн имели совп (одинак) загол (схемы). Это озн, что совп кол атриб, назв атриб и тип (домен) одноим атрибутов.

Нек отн форм не явл совместим из-за разл в назв атриб, но стан таков после примен оп переимен атрибутов.

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

Переимен В рез примен оп переимен получ новое отнош, с измен именами атриб.
Син:R RENAME Atr₁, Atr₂, … AS NewAtr₁, NewAtr₂, …

Где R — отношAtr₁, Atr₂, …— исх имена атрибутов NewAtr₁, NewAtr₂,  — новые имена атрибутов

Прим1. След оператор возвр неименов отн, в кот атр переимен в :

Объед Отн с тем же загол, что и у совмест по типу отно A и B, и телом, состоящим из кортежей, принад или A, или B, или обоим отн.Синтаксис: A UNION B

Замеч. Объед, как и любое отнош, не м содерж одинак кортежей. Поэтому, если нек кортеж входит и в отнош , и отнош , то в объед он входит один раз.

Пример 2. Пусть даны два отнош и с информацией о сотрудниках:

Отношение A Отношение B

Объединение этих отношений имеет вид

Отношение A UNION B

Пересечение

Отн с тем же загол, что и у отн A и B, и телом, сост из кортежей, принадл одновр обоим отн A и B.
Синт: A INTERSECT B

Прим. Для тех же отнош и , что и в предыд прим пересечение имеет вид:

Оп объед и пересечения являются коммутативн

Вычитание

Отн с тем же загол, что и у совмест по типу отн A и B, и телом, сост из кортежей, принадл отн A и не принадл отн B. Синтаксис: A MINUS B

Прим Для тех же отн и , что и в предыд прим вычит имеет вид:

Пр2 R1= (ФИО, Паспорт, Школа);R2= (ФИО, Паспорт, Школа);R3= (ФИО, Паспорт, Школа).

Рассм ситуац поступл в вуз, кот б характ для периода, когда были разре та н репетиц вступ экз, кото сдавались раньше осн вступ экз в вуз. Отн R1 содерж список абит, сдава репетиц экза. Отно R2 содерж список абиту, сдавав экза на общих усло. отн R3 содер список абит, принят в инст. Б счит, что при неудач сдаче репетиц экз абит мог дел 2 попытку и сдав экза в общем потоке, поэтому неко абиту могут присутств как в 1, так и во в2 отнош.

Список абит, кот поступали 2 раза и не пост в вуз:.

Список абит кот поступ в вуз с 1 раза, т. е. они сдав экза только 1 раз и сдали их так хор, что сразу были зачисл в вуз:.

Список абит, кот поступ в вуз только со 2 раза. Прежде всего это те абитур, кот присутст в отн R1 и R2, потому что они поступ 2 р, и присутст в отно R3, потому что они поступ:R = .

Список абит, кот поступ только 1 раз и не пост. Это прежде всего те абит, кот присутс в R1 и не присутст в R2, и те, кто присутс в R2 и не присутст в R1. И, разум, никто из них не присутст в R3:

Декартово произведение

Отн (A₁, A₂, …, A_m, B₁, B₂, …, B_m), загол кот явл сцепл загол отн A(A₁, A₂, …, A_m) и B(B₁, B₂, …, B_m), а тело состоит из кортежей, явл сцепл кортежей отношений A и B:

(a₁, a₂, …, a_m, b₁, b₂, …, b_m) таких, что (a₁, a₂, …, a_m)∈ A, (b₁, b₂, …, b_m)∈ B. Синт :A TIMES B

Пример 5. Пусть даны 2 отнош и с информац о поставщиках и деталях:

Отношение A (Поставщики) Отношение B (Детали)

Декартово произведение отношений и будет иметь вид:

Выборка (ограничение)

Отн с тем же загол, что и у отн A, и телом, сост из кортежей, зн атрибутов кот при подст в условие c дают зн ИСТИНА. c предст собой логич выр, в кот м вх атрибуты отн A и/или скал выраж.
Синтаксис: A WHERE c

Выборка — это оп, кот выделяет мн-во строк в таблице, удовл зад усл. Усл м б любое логич выр

Пример.Из табл с продуктами выберем все комп, продающ продуты дешевле 110.
π_COMPANYσ_(PRICEPRODUCTS

COMPANY

ООО ”Темная сторона”

ОАО ”Фрукты”

Проекция

Отн с загол (X, Y, …, Z) и телом, содерж мн-во кортежей вида (x, y, …, z), таких, для кот в отн A найд кортежи со зн атрибута X= x, зн атриб Y= y, …, зн атриб Z =z. При вып проекции выдел «вертикаль» вырезка отн-операнда с естеств уничт потенц возник кортежей-дубликатов.
Синт: A[X, Y, …, Z] Или PROJECT A {x, y, …, z}

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

Прим табл PRODUCTS. сделаем проекц на таб PRODUCTS выбр из нее ID и PRICE. π_{(ID, PRICE)} PRODUCTS. В рез этой оп получим отношение:

Исходное отнош проекция

Отношение A (Поставщики) Проекция

Соединение -есть рез послед примен оп декарт произв и выборки. Если в от имеются атрибуты с одинак наимен, то перед вып соед такие атрибуты необходимо переименовать.
Синт:(A TIMES B) WHERE c

Оп соед обратна оп проекции и создает новое отн из 2 уже существ. Новое отн получ конкатенац кортежей 1 и 2 отнош, при этом конкатенац подверг отн, в кот совп зн зад атрибутов. В частн, если соед отн PRODUCTS и SELLERS, этими атриб б атрибуты доменов ID.
оп соедин есть рез=т последоват примен опер декарт произвед и выборки. Если в отн и есть атрибуты с одинак наимен, то перед вып соедине такие атрибуты н переимен.

В дан сл усл явл равенство PRODUCTS.ID и SELLERS.ID.

Тэта-соед Пусть отн содержит атр , отн содерж атр , а - 1 из оп сравн ( и т.д.). Тогда -соед отн по атр с отн по атр наз отнош

или более коротко

Прим. Рассм комп, в кот хран данные о поставщ и поставл деталях. Пусть поставщ и деталям присв некий статус. Пусть бизнес комп организ так, что поставщ имеют право поставл только те детали, статус кот не выше статуса поставщ (см этого м б в том, что хор поставщ с высок статусом м поставл больше разновидн деталей, а плохой постав с низк статусом м поставл только огранич список деталей, важн кот (статус детали) не очень высока).

Отношение A (Поставщики) Отношение B (Детали)

Отв на вопрос "какие поставщ имеют право поставл какие детали?" дает -соедин :

Отношение "Какие поставщики поставляют какие детали"

Экви-соедНаиб важным частн сл -соед явл случ, когда есть просто равенство.

Синт экви-соединения:

Прим Пусть есть отнош , и , хран инф о поставщ, деталях и поставках

Отнош P (Поставщики) Отнош D (Детали) Отнош PD (Поставки)

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

Обыч, такой слож формой записи не польз. Но как бы то ни было, в рез имеем отношение:

Отношение "Какие детали поставляются какими поставщиками"

Недост экви-соед явл то, что если соед происх по атр с одинак наимен (а так чаще всего и происх), то в результат отн появл 2 атриб с одинак зн. В нашем прим атриб PNUM1 и PNUM2 содер дублир данные. Изб от этого недост м, взяв проекцию по всем атр, кроме одного из дублир. Именно так действ естеств соеди.

Ест соед. Пусть даны отн и , имею одинак атр (т.е. атр с одинак имен и опред на одинак доменах). Тогда ест соед отнош и наз отнош с загол и телом, содер мн-во кортежей , таких, что и

Замеч. В синт ест соед не указ, по каким атр произв соед. Ест соед произв по всем одинак атриб.

Замеч. Ест соед экв следующей последовательности реляционных операций:

1. Переименовать одинаковые атрибуты в отношениях

2. Выполнить декартово произведение отношений

3. Вып выборку по совпадающим значениям атрибутов, имевших одинаковые имена

4. Вы проекцию, удалив повторяющиеся атрибуты

5. Переименовать атрибуты, вернув им первоначальные имена

Замеч. М вып послед ест соед неск отн. Нетр пров, что ест соед (как, впрочем, и соед общего вида) обладает св-вом ассоциативности, т.е.

поэтому такие соед м запис, опуская скобки:

Прим. В предыд прим отв на вопр"какие детали поставл поставщ", б просто запис в виде ест соед 3 отн (для удоб просм порядок атриб изме, это явл доп по свойствам отношений):

Деление

Отн с загол (X₁, X₂, …, X_n) и телом, содерж мн-во кортежей (x₁, x₂, …, x_n), таких, что для всех кортежей (y₁, y₂, …, y_m) ∈ B в отн A(X₁, X₂, …, X_n, Y₁, Y₂, …, Y_m) найдется кортеж

(x₁, x₂, …, x_n, y₁, y₂, …, y_m).
Синтаксис:A DIVIDEBY B

Пусть задтдва отн - A с загол {a₁, a₂, ..., a_n, b₁, b₂, ..., b_m} и B с загол {b₁, b₂, ..., b_m}. Б считать, что атр b_i отн A и атр b_i отн B не только обл одним и тем же именем, но и опр на одном и том же домене. Наз мн-во атриб {a_j} сост атриб a, а мн-во атриб {b_j} - сост атриб b. После этого б гов о реляц делении бинарн отн A(a,b) на унарное отно B(b). Рез дел A на B явл унарное отн C(a), сост из кортежей v таких, что в отн A имеются кортежи такие, что мн-во зн {w} вкл мн-во зн атр b в отн B. У оп реляц деления 2 операнда - бинарное и унарное отн. Результир отн сост из одноатрибут кортежей, вкл зн 1го атриб кортежей 1го операнда таких, что мн-во знач 2го атрибута (при фиксир знач 1го атриб) совп со мнвом зн 2го операнда.

Предп, что в БД сотр поддерж 2 отн: СОТРУДНИКИ ( ИМЯ, ОТД_НОМ ) и ИМЕНА ( ИМЯ ), причем унарное отн ИМЕНА содерж все фамил, кот обла сотр организ. Тогда после вып операции реляц делен отн СОТРУДНИКИ на отн ИМЕНА бу получ унарное отн, содерж номера отделов, сотр кот обл всеми возм в этой организ именами.

Замеч. Типич з-сы, реализ с пом оп дел, обыч в своей ф-ке имеют слово "все" - "какие поставщ поставл все детали?".

Прим. В прим с поставщ деталями и поставк отв на вопр, "какие поставщ поставл все детали?".

В кач делим возьм проекц , содерж ном поставщ и ном поставл ими деталей: В кач делит возьм проек , содерж список ном всех деталей (не обязат поставл кем-либо):

Проекция X=PD[PNUM,DNUM]

проекция Y=D[DNUM]

Отношение X DEVIDEBY Y

Деление дает список номеров поставщиков, поставл все детали:

Оказалось, что только поставщик с ном 1 поставляет все детали.

Примеры исп реляционных операторов

Прим. Получить имена поставщ, поставл деталь номер 2.

Реш:

Прим. Получить имена поставщ, поставл по кр мере одну гайку.

Реш:

От на этот запрос м получ и иначе:

Прим. Получить имена поставщ, поставляющих все детали.

Реш:

Прим Получить имена поставщ, не поставл деталь номер 2.

Реш:

Ответ на этот запрос м получить и пошагово:

- получ список ном всех поставщ - соед данн о поставщ и поставках

- в дан о поставщ и поставк ост только дан о поставк детали номер 2.

- получить список номеров поставщ, поставл деталь номер 2.

- получить список номеров поставщ, не поставл деталь номер 2.

- соед список ном поставщ, не поставл деталь номер 2 с данн о поставщ (получ полные данные о поставщ, не постав деталь номер 2).

- иск ответ (имена поставщиков, не постав деталь номер 2).

Зависимости меж отношениями

рел модель- бд в виде мн-ва взаимосвязанн отн. В отл от теор-графовых моделей в реляц модели связи меж отношениями поддержи неявн обр. В каждой связи одно отн м выступ как осн, а др отн— в роли подч. Это озна, что один кортеж осно отн м бы связан с неск кортежами подч отн. Для поддержки этих связей оба отно до содержать наборы атрибу, по кото они связ. В осн отн это 1ичн ключ отно (PRIMARY KEY), кото однозн опр кортеж осно отн. В подч отн для моделир связи до присутств набор атриб соответ 1ично ключу осн отн. но здесь этот набор атрибутов уже явл вторич ключом, т. е. он опр мнво кортежей подч отн, кот связаны с единств кортежем осн отно Данный набор атриб в подч отн принято наз внешним ключом (FOREIGN KEY)., рассм ситуацию,, когда описать карьеру нек чел. Каждый чел в св труд деяте сменяет неск мест работы в разных орг, где он рабо в разных должно. Тогда мы д созд два отн: одно для моделир всех раб людей, а другое для моделир записей в их трудовых книжках,

Зависимые реляц опер= не все оп реляц алгебры явл независ - нек из них выр через др реляц операторы.

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

Опе пересеч выр через вычит так:

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

Таким обр показ, что оп соед, пересеч и деления м выр через др реляц операт, т.е. эти опер не явл примитивным.

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

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

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

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

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

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

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

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

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

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

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

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

1. ВЕЩЕСТВО(НОМ_ВЕЩЕСТВА, ВЕЩЕСТВО),

2. ЭЛЕМЕНТЫ(НОМ_ЭЛЕМЕНТА, ЭЛЕМЕНТ),

3. ХИМИЧ_СОСТАВ_ВЕo-В(НОМ_ВЕЩ-ВА, НОМ_ЭЛЕМЕНТА, ПРОЦЕНТ).

Отношение ВЕЩЕСТВО Отношение ЭЛЕМЕНТЫ

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

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

1. R1(НОМЕР_ВЕЩ,НОМ_ЭЛЕМ,ПРОЦЕНТ)= ХИМИЧ_СОСТАВ_ВЕЩ[ПРОЦЕНТ90]. (Выборка из отношения).

2. R2(НОМ_ЭЛЕМ) = R1[НОМ_ЭЛЕМ]. (Проекция отношения).

3. R3(НОМ_ЭЛЕМЕНТА,ЭЛЕМЕНТ)= R2[НОМ_ЭЛЕ=НОМ_ЭЛЕ]ЭЛЕМЕНТЫ. (Ест соединение)

4. ОТВЕТ(ЭЛЕМЕНТ) = R3[ЭЛЕМЕНТ]. (Проекция таблицы).

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

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

WHERE ЭЛЕМЕНТЫ.НОМ_ЭЛЕМЕНТА=ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.НОМ_ЭЛЕМЕНТА

AND ХИМИЧЕСКИЙ_СОСТАВ_ВЕЩЕСТВ.ПРОЦЕНТ90;

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

http://www.studfiles.ru/preview/5615402/page:7/

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

Пр На мн ве N опр отно. Тогда транзи замык этого отн для зна 1

Транзи замыкание отн «быть сыном» явл отн «быть прямым потомком».

Транз замыкание отн «иметь общую стену» для жильцов одного дома явл отн « жить на одном этаже».

Пр2 на мнве A={1,2,3,4} зад отн R={(1,2),(3,4),(4,2)}. отн R не симм, не рефлекс и не транзит. Замыкание R отн св-ва симметричн явл R^*={(1,2),(3,4),(4,2);(2,1),(4,3),(2,4)}. Замык R отн рефлексивн явл

 R^*={(1,2),(3,4),(4,2);(1,1),(2,2),(3,3),(4,4)}. Замык R отн транзитивно явл мнво  R^*={(1,2),(3,4),(4,2);(3,2)}.

Рефлексивное замыкание отношений

Пусть тожд отн Е состоит из упоряд пар самого себя – . Тогда R*=RE (R* – рефлекс замык, а R – транзи замыкание).Если R транзитивно и рефлексивно, то R*=R.

Пр. Исп R – отн на N такое, что получим.

След прим илл класс запросов, невыразим ср-вами реляц алгебры или реляц исчисл по прич невыразим средствами реляц алгебры транзитивного замыкания отношений (см. гл. 1).

Прим. Рассм отн, описыв сотр нек предпр. Отн содерж данные о табель ном сотр, фамилии, должн и таб номере рук-ля сотр – СОТРУДНИКИ (ТАБ_НОМ, ФАМИЛИЯ, ДОЛЖН, ТАБ_НОМ_РУК):

Отношение СОТРУДНИКИ

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

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