Тема_4 (1122340), страница 4
Текст из файла (страница 4)
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (16)Базовые операции Алгебры A (14)ПРОЕКТЫ_1ПРОЕКТЫ_1 ◄OR► НОМЕРА_ПРОЕКТОВПРОЕКТ_НАЗВПРОЕКТ_РУКПРОЕКТ_НАЗВПРОЕКТ_РУКПРО_НОМПРОЕКТ 1ИвановПРОЕКТ 1Иванов1ПРОЕКТ 2ИваненкоПРОЕКТ 2Иванов1ПРОЕКТ 3Иванов1ПРО_НОМПРОЕКТ 1Иваненко11ПРОЕКТ 2Иваненко12ПРОЕКТ 3Иваненко1ПРОЕКТ 1Иванов2ПРОЕКТ 2Иванов2ПРОЕКТ 3Иванов2ПРОЕКТ 1Иваненко2ПРОЕКТ 2Иваненко2ПРОЕКТ 3Иваненко2ПРОЕКТ 1Иванов3ПРОЕКТ 2Иваненко3НОМЕРА_ПРОЕКТОВ Предположим, что домен атрибутаПРОЕКТ_НАЗВ включает значения“ПРОЕКТ_1”, “ПРОЕКТ_2”, “ПРОЕКТ_3”,домен атрибута ПРОЕКТ_РУК ограничензначениями “Иванов”, “Иваненко”, адоменом атрибута ПРО_НОМ являетсямножество {1, 2, 3} Результат операции ◄OR► надоперандами без общих атрибутов08.10.201050С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (17)Базовые операции Алгебры A (15)ПРОЕКТЫ_1ПРО_НОМПРОЕКТЫ_2 ◄OR► НОМЕРА_ПРОЕКТОВПРОЕКТ_РУК1Иванов2ИваненкоНОМЕРА_ПРОЕКТОВПРО_НОМ1ПРО_НОМПРОЕКТ_РУК1Иванов2Иваненко2Иванов1Иваненко2 Предположим, домен атрибутаПРОЕКТ_РУК ограничен значениями“Иванов”, “Иваненко”, а доменом атрибутаПРО_НОМ является множество {1, 2, 3}08.10.2010 Результат операции ◄OR► надоперандами, схемы которыхчастично пересекаются51С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (18)Полнота алгебры (1)Покажем, что Алгебра A является полной, т.е. наоснове введенных операций выражаются всеоперации алгебры КоддаИмеются операция ◄REMOVE► в качестве аналогаоперации PROJECT, а также операцияпереименования атрибутов ◄RENAME►UNION является частным случаем операции ◄OR►,TIMES, INTERSECT и NATURAL JOIN – частныеслучаи операции ◄AND►Осталось показать, что через операции Алгебры Aвыражаются операции MINUS, ограничения(WHERE), соединения общего вида (JOIN) иреляционного деления (DIVIDE BY)08.10.201052С.Д. Кузнецов.
Базы данных.РеляционАлгебра A Дейта и Дарвена (18)Полнота алгебры (2)◄NOT► СОТРУДНИКИ_В_ПРОЕКТЕ_2СОТРУДНИКИ_В_ПРОЕКТЕ_1СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПСОТР_ОТД_НОМЕРСОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПСОТР_ОТД_НОМЕР2934Иванов11,2003102935Иванов11,2003102935Петров14,4003102936Иванов11,2003102936Сидоров9,2003132937Федоров11,0003102937Иванов11,2003102938Иванова11,2003152937Иванов11,2003102935Иванов14,400310….….….….СОТРУДНИКИ_В_ПРОЕКТЕ_2СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПСОТР_ОТД_НОМЕР2934Петров14,4003102934Иванов11,200310….….….….2935Петров14,4003102936Сидоров9,2003132939Сидоренко9,200313….….….….2940Федоренко11,000310 2941Иваненко11,2003152937Федоров11,000310….….….….2938Иванова11,200315….….….….СОТРУДНИКИ_В_ПРОЕКТЕ_1 ◄AND► ◄NOT►СОТРУДНИКИ_В_ПРОЕКТЕ_2СОТР_НОМЕРСОТР_ИМЯ2936Сидоров9,2003132937Федоров11,0003102938Иванова11,20031508.10.2010СОТР_ЗАРПСОТР_ОТД_НОМЕР Если отношения r1 и r2 совместимы пообъединению, то r1 MINUS r2 = r1◄AND► ◄NOT► r253С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (19)Полнота алгебры (3)Покажем, как можно выразить операцию ограниченияс помощью операций Алгебры A для всехдопустимых простых условийПредположим (для упрощения примеров), чтомножества значений доменов, на которыхопределены атрибуты отношения СОТРУДНИКИ_1,ограничены значениями, содержащимися в телеэтого отношенияНачнем с обсуждения операции WHERE с условиемвида a comp-op const08.10.201054С.Д. Кузнецов.
Базы данных.РеляционАлгебра A Дейта и Дарвена (20)Полнота алгебры (4)СОТРУДНИКИ_1 ◄AND► ЗАРП_11000СОТРУДНИКИ_1СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПРУК_НОМСОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПРУК_НОМ2934Иванов11,40029342937Федоров11,00029342935Петров14,40029342938Иванова11,00029412936Сидоров9,20029342940Федоренко11,00029412937Федоров11,00029342941Иваненко11,00029412938Иванова11,00029412939Сидоренко9,20029412940Федоренко11,00029412941Иваненко11,0002941 Выражение WHERE (a = const)через ◄AND►ЗАРП_11000СОТР_ЗАРП11,00008.10.201055С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (21)Полнота алгебры (5)СОТРУДНИКИ_1 ◄AND► ЗАРП_НЕ_9200СОТРУДНИКИ_1СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПРУК_НОМСОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПРУК_НОМ2934Иванов11,40029342934Иванов11,40029342935Петров14,40029342935Петров14,40029342936Сидоров9,20029342937Федоров11,00029342937Федоров11,00029342938Иванова11,00029342938Иванова11,00029412939Сидоренко9,20029412940Федоренко11,00029412940Федоренко11,00029412941Иваненко11,00029412941Иваненко11,0002941ЗАРП_НЕ_9200СОТР_ЗАРПВыражение WHERE (a ≠ const) через◄AND►11,00011,40014,40008.10.201056С.Д. Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (22)Полнота алгебры (6)Обратимся к ограничениям с условием вида a compop bОпять начнем со случая, когда comp-op = “=”Предположим, что требуется выполнить операциюСОТРУДНИКИ_1 WHERE СОТР_НОМЕР = РУК_НОМУтверждается, что результат этой операциисовпадает с результатом следующего выражения:СОТРУДНИКИ_1 ◄AND► ((((СОТРУДНИКИ_1◄REMOVE► СОТР_НОМЕР) ◄REMOVE►СОТР_ИМЯ) ◄REMOVE► СОТР_ЗАРП)◄RENAME► (РУК_НОМ, СОТР_НОМЕР))08.10.201057С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (23)Полнота алгебры (7)СОТРУДНИКИ_1 ◄AND► ((((СОТРУДНИКИ_1◄REMOVE► СОТР_НОМЕР) ◄REMOVE►СОТР_ИМЯ) ◄REMOVE► СОТР_ЗАРП)◄RENAME►(РУК_НОМ, СОТР_НОМЕР))СОТРУДНИКИ_1СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПРУК_НОМ2934Иванов11,40029342935Петров14,40029342936Сидоров9,20029342937Федоров11,00029342938Иванова11,00029412939Сидоренко9,20029412940Федоренко11,00029412941Иваненко11,0002941(((СОТРУДНИКИ_1 ◄REMOVE► СОТР_НОМЕР)◄REMOVE► СОТР_ИМЯ) ◄REMOVE► СОТР_ЗАРП)◄RENAME► (РУК_НОМ, СОТР_НОМЕР)СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРПРУК_НОМ2934Иванов11,40029342941Иваненко11,0002941Выражение WHERE (a = b) через◄REMOVE►,◄RENAME► и◄AND►СОТР_НОМЕР2934294108.10.201058С.Д. Кузнецов.
Базы данных.РеляционАлгебра A Дейта и Дарвена (24)Полнота алгебры (8)Предположим, что имеется отношение СОТРУДНИКИ_2(СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРП, РУК_НОМ,ПРО_ЗАРП) причем значениями атрибута ПРО_ЗАРП являютсясредние значения заплаты, получаемые участникамисоответствующего проекта (сотрудник может быть участникомтолько одного проекта)Пусть нас интересуют данные о сотрудниках, получающиезарплату выше средней, т.е.
нам нужен результат операцииСОТРУДНИКИ_2 WHERE (СОТР_ЗАРП > ПРО_ЗАРП)Будем считать, что множество значений доменов, на которыхопределены атрибуты СОТР_НОМЕР и СОТР_ЗАРП, ограничензначениями, присутствующими в теле отношенияСОТРУДНИКИ_2, а домен атрибута РУК_НОМ такой же, как уСОТР_НОМЕР08.10.201059С.Д. Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (25)Полнота алгебры (9)СОТРУДНИКИ_2ПРЕМ_БОЛЬШЕ_ЗАРПСЛУ_НОМЕРСЛУ_ИМЯСЛУ_ЗАРПСЛУ_ПРЕМ4434Иванов22400.0018000.004435Петров29600.0022000.004415Сидоров23000.0020000.004436Федоров20000.0022000.004440Иванова22000.0020000.004441Сидоренко18000.0022000.004416Федоренко20000.0020000.004417Иваненко22000.0020000.00СЛУЖАЩИЕ_2 ◄AND► ПРЕМ_БОЛЬШЕ_ЗАРПСЛУ_НОМЕРСЛУ_ИМЯСЛУ_ЗАРПСЛУ_ПРЕМ4436Федоров20000.0022000.004441Сидоренко18000.0022000.00СЛУ_ПРЕМСЛУ_ЗАРП20000.0018000.0022000.0018000.0022000.0020000.0022400.0018000.0022400.0020000.0022400.0022000.0023000.0018000.0023000.0020000.0023000.0022000.0023000.0022400.0029600.0018000.0029600.0020000.0029600.0022000.0029600.0022400.0029600.0023000.00 Выражение WHERE (a > b) через ◄AND►08.10.201060С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (26)Полнота алгебры (10)Операция взятия расширенного декартова произведения TIMESявляется частным случаем операции ◄AND►С помощью Алгебры A можно выполнять ограниченияПоэтому с помощью операций Алгебры A выражаются и соединенияобщего вида08.10.201061С.Д. Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (27)Полнота алгебры (11)Пусть имеются отношения r1 {A, B} и r2 {B}Утверждается, что результат r1 DIVIDE BY r2совпадает с результатом выражения (r1 PROJECT A)MINUS (((r2 TIMES (r1 PROJECT A)) MINUS r1) PROJECTA) в терминах операций реляционной алгебры Коддаили (r1 ◄REMOVE► B) ◄AND► ◄NOT► (((r2 <AND> (r1◄REMOVE► B)) ◄AND► ◄NOT► r1) ◄REMOVE► B) втерминах операций Алгебры A08.10.201062С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (28)Полнота алгебры (12)Результатом выполнения операции r1 PROJECT A являетсяунарное отношение со схемой {A}, кортежи тела которогосодержат все значения атрибута A из тела отношения r1Результат выражения r2 TIMES (r1 PROJECT A) – этоотношение со схемой {A, B}, в тело которого входят всевозможные комбинации значений атрибута B в теле отношенияr2 и атрибута A в теле r1В теле результата выражения (r2 TIMES (r1 PROJECT A))MINUS r1 останутся только кортежи с таким значением атрибутаA, что значение атрибута B, принадлежащее телу r2, неявляется значением атрибута B ни в одном кортеже телаотношения r1Проекция результата выражения (r2 TIMES (r1 PROJECT A))MINUS r1 на атрибут A содержит только те значения A, которыене должны попасть в результат операции r1 DIVIDE BY r2Выполнение завершающей операции MINUS дает желаемыйрезультат08.10.201063С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (29)Полнота алгебры (13)СОТРУДНИКИ PROJECT {СОТР_НОМЕР,СОТР_ИМЯ, СОТР_ЗАРП}СОТРУДНИКИСОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРППРО_НОМ2934Иванов11,40012935Петров14,40012936Сидоров9,20012937Федоров11,00012938Иванова11,00012934Иванов11,4002935Петров2939СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРП2934Иванов11,4002935Петров14,4002936Сидоров9,2002937Федоров11,00022938Иванова11,00014,40022939Сидоренко9,200Сидоренко9,20022940Федоренко11,0002940Федоренко11,00022941Иваненко11,0002941Иваненко11,0002НОМЕРА_ПРОЕКТОВПРО_НОМ1208.10.201064С.Д. Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (30)Полнота алгебры (14)(СОТРУДНИКИ PROJECT {СОТР_НОМЕР,СОТР_ИМЯ, СОТР_ЗАРП}) TIMESНОМЕРА_ПРОЕКТОВСОТР_НОМЕР2934293429352935293629362937293729382938293929392940294029412941СОТР_ИМЯИвановИвановПетровПетровСидоровСидоровФедоровФедоровИвановаИвановаСидоренкоСидоренкоФедоренкоФедоренкоИваненкоИваненкоСОТР_ЗАРП11,40011,40014,40014,4009,2009,20011,00011,00011,00011,0009,2009,20011,00011,00011,00011,000ПРО_НОМ1212121212121212 Выражение операции DIVIDE BY черездругие операции Алгебры A08.10.2010((СОТРУДНИКИ PROJECT {СОТР_НОМЕР,СОТР_ИМЯ, СОТР_ЗАРП})TIMES НОМЕРА_ПРОЕКТОВ) MINUS СОТРУДНИКИСОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРППРО_НОМ2936Сидоров9,20022937Федоров11,00022938Иванова11,00022939Сидоренко9,20012940Федоренко11,00012941Иваненко11,0001(СОТРУДНИКИ PROJECT {СОТР_НОМЕР, СОТР_ИМЯ,СОТР_ЗАРП}) MINUS ((((СОТРУДНИКИ PROJECT{СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРП})TIMES НОМЕРА_ПРОЕКТОВ) MINUS СОТРУДНИКИ)PROJECT {СОТР_НОМЕР, СОТР_ИМЯ, СОТР_ЗАРП})СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРП2934Иванов11,4002935Петров14,40065С.Д.
Кузнецов. Базы данных.РеляционАлгебра A Дейта и Дарвена (31)Избыточность алгебры (1)В формальной математической логике стандартнымбазисом для выражения всех возможных булевскихфункций является набор {NOT, AND, OR}Этот набор избыточен, поскольку верны тождества AAND B ≡ NOT (NOT A OR NOT B) и A OR B ≡ NOT(NOT A AND NOT B)Аналогичные тождества справедливы для операций◄NOT►, ◄AND► и ◄OR► Алгебры AВ алгебре логики существуют две операции, черезкаждую из которых выражаются все три “базовые”операции: “штрих Шеффера” – sh (A, B) ≡ NOT A ORNOT B – и “стрелка Пирса” – pi (A, B) ≡ NOT A ANDNOT08.10.201066С.Д. Кузнецов.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
