Теорминимум к экзамену по базам данных, страница 2

После этого будем говоритьо реляционном делении «бинарного» отношения A{a, b} на унарное отношение B{b}.По определению, результатом деления A на B (A DIVIDE BY B) является «унарное» отношение C{a}, тело которого состоитиз кортежей v таких, что в теле отношения A содержатся кортежи v UNION w такие, что множество {w} включает телоотношения B. Операция реляционного деления не является примитивной и выражается через операции декартовапроизведения, взятия разности и проекции. Мы покажем это в следующей лекции.Операции алгебры A: операция реляционного отрицания <NOT> (дополнения) операция реляционной конъюнкции (или дизъюнкции) операция проекции <REMOVE> (удаления атрибута)Операция <NOT>Пусть s обозначает результат операции <NOT> r.

Тогда:Hs = Hr (заголовок результата совпадает с заголовком операнда);Bs = {ts : exists tr (tr Br and ts = tr) } (в тело результата входят все кортежи, соответствующие заголовку и невходящие в тело операнда).Операция <REMOVE>Пусть s обозначает результат операции r <REMOVE> A.Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип (или домен) T такой,что <A, T> Hr (т. е. в состав заголовка отношения r должен входить атрибут A). Тогда:Hs = Hr minus {<A, T>}, т.

е. заголовок результата получается из заголовка операнда изъятием атрибута A;Bs = {ts : exists tr exists v (tr Br and v T and <A,T,v> tr and ts = tr minus {<A,T,v>})}, т. е. в тело результата входят всекортежи операнда, из которых удалено значение атрибута A.Операция <AND>Пусть s обозначает результат операции r1 <AND> r2.Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1>Hr1 и <A, T2>Hr2, то T1=T2. (Другимисловами, если в двух отношениях-операндах имеются одноименные атрибуты, то они должны быть определены наодном и том же типе (домене).) Тогда:Hs = Hr1 union Hr2, т. е.

заголовок результата получается путем объединения заголовков отношений-операндов;Bs = { ts : exists tr1 exists tr2 ((tr1Br1 and tr2Br2) and ts = tr1 union tr2)};Обратите внимание на то, что кортеж результата определяется как объединение кортежей операндов; поэтому:если схемы отношений-операндов имеют непустое пересечение, то операция <AND> работает как естественноесоединение; если пересечение схем операндов пусто, то <AND> работает как расширенное декартово произведение; если схемы отношений полностью совпадают, то результатом операции является пересечение двух отношенийоперандов.Операция <OR>Пусть s обозначает результат операции r1 <OR> r2.Для обеспечения возможности выполнения операции требуется, чтобы если <A, T1>Hr1 и <A, T2>Hr2, то должно быть T1= T2 (одноименные атрибуты должны быть определены на одном и том же типе).

Тогда:Hs = Hr1 union Hr2 (из схемы результата удаляются атрибуты-дубликаты);Bs = { ts : exists tr1 exists tr2 ((tr1Br1 or tr2Br2) and ts = tr1 union tr2)};При этом:если у операндов нет общих атрибутов, то в тело результирующего отношения входят все такие кортежи ts,которые являются объединением кортежей tr1 и tr2, соответствующих заголовкам отношений-операндов, и хотябы один из этих кортежей принадлежит телу одного из операндов; если у операндов имеются общие атрибуты, то в тело результирующего отношения входят все такие кортежи ts,которые являются объединением кортежей tr1 и tr2, соответствующих заголовкам отношений-операндов, еслихотя бы один из этих кортежей принадлежит телу одного из операндов, и значения общих атрибутов tr1 и tr2совпадают; если же схемы отношений-операндов совпадают, то тело отношения-результата является объединением телоперандов.Операция <RENAME>Пусть s обозначает результат операции r <RENAME> (A, B).Для обеспечения возможности выполнения операции требуется, чтобы существовал некоторый тип T, такой, что <A, T>Hr, и чтобы не существовал такой тип T, что <B, T> Hr.

(Другими словами, в схеме отношения r должен присутствоватьатрибут A и не должен присутствовать атрибут B.) Тогда:Hs = (Hr minus {<A, T>}) union {<B, T>}, т. е. в схеме результата B заменяет A;Bs = {ts : exists tr exists v (tr Br and v T and <A, T, v> tr and ts = (tr minus {<A, T, v>}) union {<B, T, v>})}, т.

е. вкортежах тела результата имя значений атрибута A меняется на B.Реляционное исчисление – прикладная ветвь формального механизма исчисления предикатов первого порядка. Воснове исчисления лежит понятие переменной с определенной для нее областью допустимых значений и понятиеправильно построенной формулы, опирающейся на переменные, предикаты и кванторы. В зависимости от того, чтоявляется областью определения переменной, различают исчисление кортежей и исчисление доменов.Простые условия – операции сравнения скалярных значений (значений атрибутов переменных или литерально заданныхконстант). По определению, простое сравнение является WFF, а WFF, заключенная в круглые скобки, представляет собойпростое сравнение.Сложные WFF – строятся с помощью логических связок NOT, AND, OR и IF ...

THEN26) с учетом обычных приоритетовопераций (NOT > AND > OR) и возможности расстановки скобок.EXISTS var (form) – формула принимает значение true в том и только в том случае, если в области определенияпеременной var найдется хотя бы одно значение (кортеж), для которого WFF form принимает значение true.FORALL var (form) – формула принимает значение true, если для всех значений переменной var из ее областиопределения WFF form принимает значение true.Свободные переменные – все переменные, входящие в WFF, при построении которой не использовались кванторы.Связанная переменная –если имя переменной использовано сразу после квантора при построении WFF вида EXISTS var(form) или FORALL var (form), то в этой WFF и во всех WFF, построенных с ее участием, var является связаннойпеременной.Целевой список – компонент, который определяет набор и имена атрибутов результирующего отношения. Целевойсписок строится из целевых элементов, каждый из которых может иметь следующий вид:var.attr, где var – имя свободной переменной соответствующей WFF, а attr – имя атрибута отношения, накотором определена переменная var; var, что эквивалентно наличию подсписка var.attr1, var.attr2, ..., var.attrn, где {attr1, attr2, ..., attrn} включаетимена всех атрибутов определяющего отношения; new_name = var.attr; new_name – новое имя соответствующего атрибута результирующего отношения.Выражением реляционного исчисления кортежей называется конструкция вида target_list WHERE WFF.Условия членства.

Если R – это n-арное отношение с атрибутами a1, a2, ..., an, то условие членства имеет вид R (a i1 : vi1, ai2 :vi2, ..., aim : vim) (m  n), где vij – это либо литерально задаваемая константа, либо имя доменной переменной. Условиечленства принимает значение true в том и только в том случае, если в отношении R существует кортеж, содержащийуказанные значения указанных атрибутов.Функциональная зависимость (FD).

Пусть задана переменная отношения R, и X и Y являются произвольнымиподмножествами заголовка R («составными» атрибутами). В значении переменной отношения R атрибут Yфункционально зависит от атрибута X в том и только в том случае, если каждому значению X соответствует в точностиодно значение Y. R.XR.Y. X является детерминантом (определителем) для Y, а Y является зависимым от XFD AB называется тривиальной, если AB (т. е. множество атрибутов A включает множество B или совпадает смножеством B).+Замыканием множества FD S является множество FD S , включающее все FD, логически выводимые из FD множества S.FD AC называется транзитивной, если существует такой атрибут B, что имеются функциональные зависимости AB иBC и отсутствует функциональная зависимость CA.Аксиомы Армстронга.

Пусть A, B и C являются (в общем случае, составными) атрибутами отношения R. Множества A, B иC могут иметь непустое пересечение. Для краткости будем обозначать через AB A UNION B. Тогда:1. если BA, то AB (рефлексивность);2. если AB, то ACBC (пополнение);3. если AB и BC, то AC (транзитивность).Расширения Дейта4. AA (самодетерминированность)5.

если ABC, то AB и AC (декомпозиция)6. если AB и AC, то ABC (объединение)7. если AB и CD, то ACBD (композиция)8. если ABC и BD, то ABCD (накопление)Пусть заданы отношение R, множество Z атрибутов этого отношения (подмножество заголовка R, или составной атрибут+R) и некоторое множество FD S, выполняемых для R. Тогда замыканием Z над S называется наибольшее множество Zтаких атрибутов Y отношения R, что FD ZY входит в S+.+Алгорититм нахождения Z .Рассмотрим множество T.

На первом шаге оно равно Z.На каждом следующем шаге рассматриваем все связи AB из множества S, и если A  T, то T = T UNION B.Алгоритм завершается, когда T не поменялось на очередном шаге.Суперключом отношения R называется любое подмножество K заголовка R, включающее, по меньшей мере, хотя быодин возможный ключ R.Множество FD S2 называется покрытием множества FD S1, если любая FD, выводимая из S1, выводится также из S2.++Два множества FD S1 и S2 называются эквивалентными, если каждое из них является покрытием другого, т. е. S1 = S2 .Множество FD S называется минимальным в том и только в том случае, когда удовлетворяет следующим свойствам:1.2.правая часть любой FD из S является множеством из одного атрибута (простым атрибутом);детерминант каждой FD из S обладает свойством минимальности; это означает, что удаление любого атрибута+из детерминанта приводит к изменению замыкания S , т.