Базы Данных, 12 лекция (от 13 октября)

Материал из ESyr's Wiki pages.

БД 13.10.06

Тривиальная функциональная зависимость A -> B A >= B {СЛУ_НОМ, СЛУ_ИМЯ} -> {СЛУ_НОМ}

Основное свойство – всегда выполняется.

Любой тривиальный атрибут функционально определяет сам себя.

Их можно не учитывать.

Замыкание множества FD: S-множество FD S+ называется замыканием S, если S+ включает все функциональные зависимости, которые выводятся из S.

Если функциональная зависимость является правильной, то и то, что из неё следует, является правильным.

Вернемся к отношению {СЛУ_НОМ, СЛУ_ИМЯ} -> {СЛУ_НОМ} Отношение СЛУ_НОМ -> {СЛУ_ЗАРП, ОТД_НОМ} определяет парочку 1.СЛУ_НОМ -> СЛУ_ЗАРП 2.СЛУ_НОМ -> ОТД_НОМ СЛУ_НОМ -> ОТД_НОМ ОТД_НОМ -> ПРОЕКТ_РУК это плохая зависимость. Транзитивные функциональные зависимости ... высшая форма, которую можно достичь с помощью ... зависимостей. Из этой пары выводится такая пара: СЛУ_НОМ -> ПРОЕКТ_РУК

Функ пара называется A -> C транзитивной, если существует такая пара A -> B, A -> C, причём нет C -> A

Это очень нехороший вид зависимостей, который надо избегать.

Зачем существует завмыкание. Когда начинаем зависимости высчитаывать, то можно обратить внимание на достаточно полный их набор, но читсо конструктивно в них могут не попасть зависимости, которые выводятся логически, но на них не обратили внимание. В замыкании есть все зависимости – полный обзор. Ничего хорошего в том, что расширяем множество нет, но это промежуточный шаг. Следующийц – построение покрытие, из которого выделяется базис, в котором остаются все интересные функциональные зависимости.

Логический вывод, и какими правилами теория РБД предланает пользоваться.

Набор правил, которые называются аксиомами Армстронга: Интересны два факта, это не аксиомы, а праввила вывода, аксиомы – историческая шарада. Эти правила следуют из определения функц зависимостей. Армстронг предложил их три: A, B, C являются атрибутами отношения r. Составные атрибуты (до конца главы) – некрое подмножество заголовка отношения (множества ...). Необязательно A пересечение B = пустое множество. AB = A union B. 1.Аксиома рефлексивности. Если B является подмножеством A, то B функционально зависит от A. Её доказывать не надо, это настолько элементарно, что доказывать не следует 2.Если есть функ зав B от A, то существует функциональность зависим AC от BC – аксиома пополнения 3.Аксиома транзитивности. Если есть зависимость B от A и C от B, то существует функ зав C от A. Любую ФЗ, которую можно доказать, что она выводится из другой ФЗ, можно доказать с помощью этих правил. Эти правила не приведут к появлению лишних ФЗ.

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

//педедыв

Доказательства: //t1{AC} – краткое значение проекции t1 PROJECT {AC} 2.Пусть ФЗ AC->BC не выполняется. То есть найдется такое допустимое тело отношения что там найдутся два кортежа т1 т2 таки, что t1{AC}=t2{AC}, но t1{BC}!=t2{BC}. По рефлексивности следует, что t1{A} = t2{A}, из A->B следует t1{B}=t2{B}, тогда t1{C}!=t2{C}, что противоречит тривиальной ФЗ AC->C 3.2юСуществует t1, t2 t1{A}=t2{A}, но t1{C}!=t2{C}. Из A->B следует t1{B}=t2{B}. Из B->C следует t1{C}=t2{C}. Лектор с удовольствием порекомендовал бы статью Армстронга, если бы мог, потому что 1. не переведена на русский 2. нет в интернете 3. нет у лектора

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

Лектор выидел две системы дополненния Аксиом - (..., ..., ..., ...) и Дейты. Дейта лектору нравится больше.

Можно поразмышлять, чем можно заменить теоремы Армстронга.

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

Заслуга А в том, что он нашёл полезные правила, которые применяются вполне успешно.

Дополнительные аксиомы (по Дейте): Лектор сильно уважает заслуги Д за алгебру, за теорию типов, поэтому хочет, чтобы на экзамене мы это знали. Ер знания дополн аксиом он не требуется. Но лектро хочет чтобы мы смогли ответить, выводится данное им на экзамене правило из аксиом А, и если да, то как. 4.A->A. Самодетерминированностьь 5.Декомпозиция: A->BC => A->B, A->C. Как до казывается: из аксиомы 1 BC->B, из 3 A->B, из аксиомы 1 BC->C, из 3 A->C. 6.Если есть функциональные зависимости A->B, A->C, то A->BC Объединение. Из (2) A->AB AB->BC из (3) A->BC. Дальше доказывайте сами, лектор не будет. 7.Если A->B и C->D, то AC->BD – Композиция. Доказывается совершенно тоже тривиальным образом без всяких проблем. 8.Накопление – если есть A->BC и B->D, то есть A->BCD. Лектор хочет предупредить: эта простота теории может привести к желанию эту теорию развивать, но преждле чем развивать, нужно почитать, потому что 99 и 9 процентов того, что развивать, сделано более 25 лет назад. Поле всё растоптано. И если вы найдёте тропочку, которая не протоптана, то это уже большое достижение.

На самом деле, часть теории лектора близится к концу, но чуть-чуть ещё есть.

Определение: замыкание множества атрибутов. Пусть есть отношение r, Z – множество атрибутов, принадлежит Hr, S – множество FD над r, То замыкание S – наибольшее множество Z* атрибутов y принадлежит Hr, что FD Z->Y принадлежит S+.

На всякий случай лектор раскрутится чуточку назад. И вкратце повторяет всю лекцию.

Доказательство того, что множества ФЗ конструктивное, то есть алгоритм, которым можно посчитать это множество. Лектор его напишет. Легко убедиться, что этот алгоритм сходится. По построению условиям он удовлетворяет.

K:=0; Z[0]:=Z;

DO K:=K+1; Z[K]:=Z[K-1] FOREACH FD A->B IN S DO IF A<=Z[K] THEN Z[K]:=(Z[K] UNIUON B) END DO; UNTIL Z[K]=Z[K-1] Z+:=Z[K]

Доказательство: Пусть есть отношение с заголовком r{A,B,C,D,E,F} Задано множество зависимостей S={A->D, AB->E, BF->E, CD->, E->C} нужно найти замыкание {AE}+ над S 1.Z[1]=AE A->D и E->G 2.Z[2]=ACDE 3.Z[3]=ACDEF Эта штука равна предыдущему значению, и это и будет замыканием атрибутов.

Когда мы смотрим на замыканием, мы хотим узнать, входит ли ФЗ в него. Если мы найдем атрибут, то мы получим ответ.

Суперключ отношения: Это понятие пригодится, и это хорошо для того, чтобы был порядок в голове Ключи: Все в современной теории ключи равноправны. В SQL это не так. 1.Возможный ключ (candidate key) 2.Внешние ключи (foreign key) 3.Суперключ (superkey) - любое надмножество атрибутов заголовков отношения, которое включает хотя бы один возможный ключ Если некоторый атрибут K принадлежит Hr, то он является суперключом тогда и только тогда, если для любого A<=Hr выполняется K->A.

В терминах этого замечательного определения множества атрибутов в том случае, если K+ совпадает с K.

Следующее понятие: покрытие множества ФЗ. Множество ФЗ S2 есть покрытие S1 т и тт, когда любая ФЗ, выводимая из S1, выводится из S2.

Замыкание покрытием являются, но оно не интересно, так как оно очень большое. Нам интересны минимальные покрытия.

S2 покрытие т и тт, когда S1+<=S2+ (в частности, совпадают)

Два множества ФЗ называются эквивалентными, если их замыкания совпадают.