Вордовские лекции (1121814), страница 8

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

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

СЛУ_НОМ -> СЛУ_ЗАРП

СЛУ_НОМ -> ПРО_НОМ

СЛУ_НОМ -> ПРОЕКТ_РУК

{СЛУ_НОМ, СЛУ_ИМЯ} -> СЛУ_НОМ

{СЛУ_НОМ, СЛУ_ИМЯ} -> СЛУ_ЗАРП

{СЛУ_НОМ, СЛУ_ИМЯ} -> ПРО_НОМ

{СЛУ_НОМ, СЛУ_ИМЯ} -> {СЛУ_ЗАРП, ПРО_НОМ}

...

ПРО_НОМ -> ПРОЕК_РУК

У всех зависимостей разные имена. Если это правильно отражает предм область, то есть и такие зависимости (из того, что имена разные):

(2)

СЛУ_ИМЯ -> СЛУ_ЗАРП

СЛУ_ИМЯ -> ПРОЕКТ_РУК

(3)

СЛУ_ЗАРП -> ПРО_НОМ

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

Начальник является характеристикой проекта, а не служащего, пожтому они и размножились в диких количествах.

БД 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}

1. Пусть ФЗ 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

2. 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. нет у лектора

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

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

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

Эта штука сугубо практическая.

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

б) их можно придумать очень многозначная

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

Дополнительные аксиомы (по Дейте):

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

1. A->A. Самодетерминированностьь

2. Декомпозиция: A->BC => A->B, A->C. Как до казывается: из аксиомы 1 BC->B, из 3 A->B, из аксиомы 1 BC->C, из 3 A->C.

3. Если есть функциональные зависимости A->B, A->C, то A->BC Объединение. Из (2) A->AB AB->BC из (3) A->BC. Дальше доказывайте сами, лектор не будет.

4. Если A->B и C->D, то AC->BD – Композиция. Доказывается совершенно тоже тривиальным образом без всяких проблем.

5. Накопление – если есть 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

1. Z[2]=ACDE

1. 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+ (в частности, совпадают)

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

БД

Виды ФЗ

Предварительные этапы проектирования БД. Человек должен рпоанализировать предметную область, каким образом атрибуты предм области, какие между ними существуют зависимости. Самый простой вид – функциональный. Множество всех ФЗ очень фирокое, для сужения его и оставления только тех, которые представляют интерес, можно построить покрытие.

//Определение покрытия

Переходим к минимизации:

S2 покрывает S1 т и тт, когда S1+ <= S2+, эквивалентны, когда S1+=S2+

Минимальное множество ФЗ:

S {FD} – минимальное, если удовл следующим свойствам

1. правая часть любой ФЗ, принадл S состоит из одного атрибута

2. детерминант любой ФЗ из S минимален

Минимальный детерминант:

Детерминант ФЗ минимален, если при удалении любого атрибута изменяетсязамыкание.

1. Удаление любой ФЗ приводит к изменению замыкания

Примеры:

Есть отношение СЛУЖАЩИЕ_ПРОЕКТЫ

{СЛУ_НОМ (возможный ключ), СЛУ_ИМЯ, СЛУ_ЗАРП, ПРО_НОМ, ПРОЕКТ_РУК }

{FD} {СЛУ_НОМ – СЛУ_ИМЯ, СЛУ_НО – СЛУ_ЗАРП, СЛУ_НОМ – ПРО_НОМ, СЛУ_НОМ – ПРОЕК_РУК, ПРО_НОМ – ПРОЕКТ_РУК} – МИНИМАЛЬНОЕ

(*) {СЛУ_НОМ – {СЛУ_ИМЯ, СЛУ_ЗАРП}, СЛУ_НОМ – ПРО_НОМ, СЛУ_НОМ – ПРОЕКТ_РУК, ПРО_НОМ – ПРОЕКТ_РУК} – не минимально, по 1

S- - минимальное множество

Общая схема построения:

1. С использованием аксиомы декомпозиции 5 приводим множество S к эквивалентному, удовлетворяющему 1

2. Пробуем выбросить ФЗ

Пример:

r{A, B, C, D} S={A-B, A-BC, AB-C, AC-D, B-C}

SL = {A-B, A-C, AB-C, AC-D, B-C}

почему можно удалить AC-D: A-C, A-AC, A-D

S- = {A-B, A-D, B-C}

Процедура трудоёмкая, делается достаточно долго.

S – множество ФЗ

Минимальным покрытием S является любое эквивалентное миним множество S1.

Декомпозиция отношения без потерь

В чем состоит классич проектироание РБД: на основе заголовков и отношений построить новую схему, котора в соотв с этими зависимостями будет обладать более хорошими свойстваим.

Декомп назыв декомп без потерь, это когда потом если у нас будет БД, наполненая кортежами, то если мы сделаем естественное слияние, то мы получим донормализовонное состояние без потерь.

Потери заключпаются в появлении лишних кортежей.

Есди сделать Join, то появятся лишние записи

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

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

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