Тема_4 (1122340), страница 5

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 5)

Базы данных.РеляционАлгебра A Дейта и Дарвена (32)Избыточность алгебры (2)sh (A, A) ≡ NOT A;sh (NOT A, NOT B) ≡ A OR B, иNOT sh (A, B) ≡ A AND Bpi (A, A) ≡ NOT A;pi (NOT A, NOT B) ≡ A AND B иNOT pi (A, B) ≡ A OR BАналогичные тождества справедливы для реляционных вариантовштриха Шеффера (◄sh► (r1, r2) ≡ ◄NOT► r1 <OR► ◄NOT► r2) истрелки Пирса (◄pi► (r1, r2) ≡ ◄NOT► r1 ◄AND ► ◄NOT► r2)Поэтому можно свести набор операций Алгебры A до трехопераций: ◄sh► (или ◄pi►), ◄RENAME► и ◄REMOVE ►.Покажем, что избыточна и операция ◄RENAME►08.10.201067С.Д. Кузнецов.

Базы данных.РеляционАлгебра A Дейта и Дарвена (33)Избыточность алгебры (3)ПРО_НОМ-НОМЕР_ПРОЕКТАПРО_НОМНОМЕР_ПРОЕКТА1122СОТРУДНИКИ ◄AND ► ПРО_НОМ-НОМЕР_ПРОЕКТАСОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРППРО_НОМНОМЕР_ПРОЕКТА2934293529362937293829342935293929402941ИвановПетровСидоровФедоровИвановаИвановПетровСидоренкоФедоренкоИваненко11,40014,4009,20011,00011,00011,40014,4009,20011,00011,00011111222221111122222(СОТРУДНИКИ ◄AND ► ПРО_НОМ-НОМЕР_ПРОЕКТА) ◄ REMOVE ► (ПРО_НОМ) Избыточность операции◄RENAME► Тем самым, можносократить набор операцийАлгебры A до двух операций:◄sh► (или ◄pi►) и◄REMOVE►08.10.2010СОТР_НОМЕРСОТР_ИМЯСОТР_ЗАРП2934293529362937293829342935293929402941ИвановПетровСидоровФедоровИвановаИвановПетровСидоренкоФедоренкоИваненко11,40014,4009,20011,00011,00011,40014,4009,20011,00011,00068С.Д.

Кузнецов. Базы данных.НОМЕР_ПРОЕКТА1111122222РеляционРеляционное исчисление (1)Реляционное исчисление является прикладной ветвьюформального механизма исчисления предикатовпервого порядка.В основе исчисления лежат понятия переменной с определенной для нее областьюдопустимых значений и правильно построенной формулы, опирающейся напеременные,предикаты икванторыВ зависимости от того, что является областьюопределения переменной, различают исчисление кортежей и исчисление доменов08.10.201069С.Д. Кузнецов. Базы данных.РеляционРеляционное исчисление (2) В исчислении кортежей областями определенияпеременных являются тела отношений базы данных, т.

е. допустимым значением каждой переменнойявляется кортеж тела некоторого отношения В исчислении доменов областями определенияпеременных являются домены, на которыхопределены атрибуты отношений базы данных, т. е. допустимым значением каждой переменнойявляется значение некоторого домена. Начала сравнительно подробно рассмотримисчисление кортежей, а затем коротко опишемособенности исчисления доменов08.10.201070С.Д. Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей (1)Кортежные переменные (1)Для определения кортежной переменнойиспользуется оператор RANGEНапример, для того чтобы определитьпеременную СЛУЖАЩИЙ, областьюопределения которой является значениеотношения СЛУЖАЩИЕ, нужно употребитьконструкциюRANGE СЛУЖАЩИЙ IS СЛУЖАЩИЕИ этого определения следует, что в любоймомент времени переменная СЛУЖАЩИЙпредставляет некоторый кортеж отношенияСЛУЖАЩИЕ08.10.201071С.Д. Кузнецов.

Базы данных.РеляционРеляционное исчисление кортежей (2)Кортежные переменные (2)При использовании кортежных переменных вформулах можно ссылаться на значениеатрибута переменнойаналогично тому, как, например, при программированиина языке C можно сослаться на значение поляструктурной переменнойНапример, для того, чтобы сослаться назначение атрибута СЛУ_ИМЯ переменнойСЛУЖАЩИЙ, нужно употребить конструкциюСЛУЖАЩИЙ.СЛУ_ИМЯ08.10.201072С.Д. Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей (3)Правильно построенные формулы (1)Правильно построенная формула (Well-FormedFormula, WFF) служит для выражения условий,накладываемых на кортежные переменныеОсновой WFF являются простые условия,представляющие собой операции сравненияскалярных значенийзначений атрибутов переменных или литеральнозаданных константНапример, конструкцииСЛУЖАЩИЙ.СЛУ_НОМ = 4434 иСЛУЖАЩИЙ.СЛУ_НОМ = ПРОЕКТ.ПРОЕКТ_РУКявляются простыми условиями.08.10.201073С.Д.

Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей (4)Правильно построенные формулы (2)Первое условие принимает значение true в том итолько в том случае, когда значение атрибутаСЛУ_НОМ кортежной переменной СЛУЖАЩИЙравно 4434Второе условие принимает значение true в том итолько в том случае, когда значения атрибутовСЛУ_НОМ и ПРОЕКТ_РУК переменныхСЛУЖАЩИЙ и ПРОЕКТ совпадают.По определению, простое сравнение являетсяWFF, а WFF, заключенная в круглые скобки,представляет собой простое сравнение.08.10.201074С.Д.

Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей (5)Правильно построенные формулы (3)Более сложные варианты WFF строятся из WFF и простыхсравнений с помощью логических связок NOT, AND, OR иIF ... THEN IF a THEN b ≡ NOT a OR bс учетом обычных приоритетов операций (NOT > AND > OR)и возможности расстановки скобокТак, если form – WFF, а comp – простое сравнение, то NOT form, comp AND form, comp OR form и IF comp THEN formявляются WFF08.10.201075С.Д.

Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей (6)Правильно построенные формулы (4)Для примеров воспользуемся возможными значениямиотношений СЛУЖАЩИЕ, ПРОЕКТЫ и НОМЕРА_ПРОЕКТОВ08.10.201076С.Д. Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей (7)Правильно построенные формулы (5)ФормулаIF СЛУЖАЩИЙ.СЛУ_ИМЯ = ‘Иванов’THEN (СЛУЖАЩИЙ.СЛУ_ЗАРП >= 22400.00 ANDСЛУЖАЩИЙ.ПРО_НОМ = 1)будет принимать значение true для следующего множествазначений кортежной переменной СЛУЖАЩИЙ08.10.201077С.Д.

Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей (8)Правильно построенные формулы (6)Нужно представлять себе какой-нибудь способ реализациисистемы, которая сможет по заданной WFF при существующемсостоянии базы данных произвести такой результатОчевидным способом является следующий:В некотором порядке просмотреть область определения переменной и ккаждому очередному кортежу применить условиеРезультатом будет то множество кортежей, для которых привычислении условия производится значение trueРезультат подобной интерпретации формулы эквивалентенрезультату выполнению алгебраической операцииСЛУЖАЩИЕ WHERE (NOT (СЛУЖАЩИЙ.СЛУ_ИМЯ = ‘Иванов’) OR(СЛУЖАЩИЙ.СЛУ_ЗАРП >= 22400.00 ANDСЛУЖАЩИЙ.ПРО_НОМ = 1)над отношением, тело которого представляет собой областьопределения кортежной переменной08.10.201078С.Д.

Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей (9)Правильно построенные формулы (7)Пусть имеется следующее определение кортежной переменнойПРОЕКТ:RANGE ПРОЕКТ IS ПРОЕКТЫФормулаСЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУКбудет принимать значение true для следующего множества парзначений кортежных переменных СЛУЖАЩИЙ и ПРОЕКТ08.10.201079С.Д. Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(10)Очевидныйспособ реализациикоторая поПравильнопостроенныеформулысистемы,(8)заданной WFF при существующем состоянии базы данныхпроизводит такой результат, заключается в следующем: в некотором порядке просматривать область определения(например) переменной СЛУЖАЩИЙ; для каждого текущего кортежа из области определенияпеременной СЛУЖАЩИЙ просматривать областьопределения переменной ПРОЕКТ; оставлять в области истинности те пары кортежей, длякоторых формула принимает значение trueВозможен и альтернативный подход: начать просмотр собласти определения переменной ПРОЕКТ, и для каждогокортежа ПРОЕКТ просматривать область определенияСЛУЖАЩИЙ08.10.201080С.Д.

Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(11)Здесь нужносделать тризамечанияПравильнопостроенныеформулы(9)Во-первых, если бы в данном случае формула былатождественно истинной, например, имела вид(СЛУЖАЩИЙ.СЛУ_ИМЯ = СЛУЖАЩИЙ.СЛУ_ИМЯ) AND(ПРОЕКТ.ПРОЕКТ_РУК = ПРОЕКТ.ПРОЕКТ_РУК)),то областью истинности этой формулы являлось быдекартово произведение (в строгом математическомсмысле) тел отношений СЛУЖАЩИЙ и ПРОЕКТВ подобных случаях областью истинности WFF являетсяотношение, заголовок которого представляет собойобъединение заголовков отношений, на телах которыхопределены кортежные переменные, а кортежи получаютсяпутем объединения соответствующих кортежей из областейопределения переменных08.10.201081С.Д.

Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(12)При этомимя атрибутарезультирующегоПравильнопостроенныеформулы(10)отношенияуточняется именем соответствующей переменнойПоэтому правильнее изображать область истинностиформулыСЛУЖАЩИЙ.СЛУ_ИМЯ = ПРОЕКТ.ПРОЕКТ_РУКследующим образом:08.10.201082С.Д. Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(13)Во-вторых,как видно, показанноерезультирующееПравильнопостроенныеформулы (11)отношение в точности совпадает с результатомалгебраической операцииСЛУЖАЩИЕ JOIN ПРОЕКТЫ WHERE СЛУ_ИМЯ = ПРОЕКТ_РУКс учетом особенности именования атрибутоврезультирующего отношения.Наконец, заметим, что описанный выше способ реализации,который приводит к получению области истинностирассмотренной формулы, в действительности являетсянаиболее общим (и зачастую неоптимальным) способомвыполнения операций соединения он называется методом вложенных циклов – nested loops join08.10.201083С.Д.

Кузнецов. Базы данных.РеляционРеляционное исчисление кортежей(14)При построенииWFF допускаетсяиспользование кванторовПравильнопостроенныеформулы (11)существования (EXISTS) и всеобщности (FORALL)Если form – это WFF, в которой участвует переменная var, токонструкции EXISTS var (form) и FORALL var (form)представляют собой WFFПо определению, формула EXISTS var (form) принимаетзначение true в том и только в том случае, если в областиопределения переменной var найдется хотя бы однозначение (кортеж), для которого WFF form принимаетзначение trueФормула FORALL var (form) принимает значение true, еслидля всех значений переменной var из ее областиопределения WFF form принимает значение true08.10.201084С.Д.

Характеристики

Список файлов лекций