Заглавная страница Избранные статьи Случайная статья Познавательные статьи Новые добавления Обратная связь КАТЕГОРИИ: АрхеологияБиология Генетика География Информатика История Логика Маркетинг Математика Менеджмент Механика Педагогика Религия Социология Технологии Физика Философия Финансы Химия Экология ТОП 10 на сайте Приготовление дезинфицирующих растворов различной концентрацииТехника нижней прямой подачи мяча. Франко-прусская война (причины и последствия) Организация работы процедурного кабинета Смысловое и механическое запоминание, их место и роль в усвоении знаний Коммуникативные барьеры и пути их преодоления Обработка изделий медицинского назначения многократного применения Образцы текста публицистического стиля Четыре типа изменения баланса Задачи с ответами для Всероссийской олимпиады по праву Мы поможем в написании ваших работ! ЗНАЕТЕ ЛИ ВЫ?
Влияние общества на человека
Приготовление дезинфицирующих растворов различной концентрации Практические работы по географии для 6 класса Организация работы процедурного кабинета Изменения в неживой природе осенью Уборка процедурного кабинета Сольфеджио. Все правила по сольфеджио Балочные системы. Определение реакций опор и моментов защемления |
Алгоритм проверки схемы БД на обладание свойством сохранения ФЗ
ρ =(R 1... R n) Алгоритм: 1) построить условно-неизбыточное покрытие (УНП), взять H =∅; 2) каждую ФЗ из УНП разбить на совокупность ФЗ с одним атрибутом в правой части, то есть заменить X → A 1 A 2... A k на X → A 1, X → A 2,..., X → A k. Обозначить полученную ФЗ как G; 3) выбрать очередную ФЗ из G. Найти такую схему отношения R i, для которой справедливо включение XA ⊆ R i. Если такой схемы отношений не существует, то поместить ФЗ X → A в множество H; 4) если все ФЗ из G рассмотрены, то перейти к следующему пункту, иначе к предыдущему; 5) если H пусто, то завершить алгоритм. ρ обладает свойством сохранения ФЗ. Иначе перейти к следующему пункту; 6) просмотреть все ФЗ из H. Если какая-либо ФЗ X → A ∈ H не выводится из множества G − H, то завершить алгоритм. ρ не обладает свойством сохранения ФЗ. Иначе завершить алгоритм, и тогда ρ обладает свойством сохранения ФЗ.
Лекция №5 - Третья нормальная форма
Свойства "хорошей" схемы БД Свойство сохранения ФЗ Алгоритм проверки схемы БД на обладание свойством сохранения ФЗ Пример 1 Пусть R =(A, B, C), ρ =(AB, BC)=(R 1, R 2) и F =(A → B, B → C) Обладает ли ρ сохранением ФЗ? Смотрим: 1) H =∅, УНП=(A → BC, B → C) 2) G =(A → B, A → C, B → C) 3) A → B, AB ⊆ R 1 A → C, AC ⊈ R 2, H =(A → C) B → C, BC ⊆ R 2 4) пропускаем, так как не выполнилось условие в 3) 5) H не пустое. 6) выполняется ли A → C ∈(G − H)+=(A → B, B → C)+ A += ABC, C ∈ A +, значит ρ обладает сохранением ФЗ. Пример 2 Пусть R =(A, B, C), ρ =(AB, AC)=(R 1, R 2) и F =(A → B, B → C) Обладает ли ρ сохранением ФЗ? 1-4) H =∅, УНП=(A → BC, B → C) H =(B → C)) 5) H не пустое. 6) выполняется ли B → C ∈(G − H)+=(A → BC)+ B += B, C ∉ B +, значит ρ не обладает сохранением ФЗ. Ключ схемы отношения Ключ схемы отношения – это подмножество исходной схемы, состоящая из одного или нескольких атрибутов, которые задают уникальность значений в кортежах отношений. Если атрибут A i ∈ R входит в какой-либо ключ схемы отношения R, то он называется первичным. А если не входит ни в один, то называется непервичным. Пусть R =(A 1... A n) - некоторая схема отношения. F - множество ФЗ. Тогда X ⊆ R называется ключом схемы, если выполняются: · X → A 1... A n ∈ F + · ∀ Z ⊂ X, Z → A 1... A n ∉ F +. То есть X содержит минимальное число атрибутов, для которых выполняется предыдущее свойство.
Алгоритм построения ключа Базируется на определении ключа. Позволяет построить только один ключ. 1) i =0, X 0= A 1... A n 2) цикл по атрибутам A j в X i Если (X i − A j)+= R, то X i +1= X i − A j, i = i +1 и выйти из цикла; иначе продолжить цикл 3) если i возросло, то перейти к шагу 2); иначе X = X i - это найденный ключ. Пример построения ключа Пусть R =(A, B, C, D), F =(AB → DC, BC → AD) Надо построить ключ. 1) i =0, X 0= ABCD 2) (X 0− A)+=(BCD)+= BCDA = R, значит X 1= BCD, i =1 3) i, как видим, возросло, значит опять 2) 2) (CD)+= CD ≠ R (BD)+= BD ≠ R (BC)+= BCAD = R, X 2= BC, i =2 3) i, как видим, возросло, значит опять 2) 2) C += C ≠ R B += B ≠ R 3) i, как видим, не возросло. Значит, X = BC - ключ. Но не единственный, X = AB - тоже ключ, просто у нас получился сначала этот. Значит, A, B, C - первичные атрибуты, а D - непервичный. Третья нормальная форма Отношение находится в 3НФ, если не существует тройки:
для которой выполняются:
Если такую тройку можно найти, то схема не находится в 3НФ. Если схема отношения находится в 3НФ, то в большинстве случаев эта схема отношения не обладает аномалиями. Но существуют условия, когда схема в 3НФ обладает этими аномалиями. Хотя, встречаются они редко. Вот они:
Пример 1 Пусть R =(A, B, C, D), F =(A → B, AC → D) и ρ = R Доказать, что это отношение не находится в 3НФ. Доказываем: 1) i =0, X 0= ABCD 2) (BCD)+= BCD ≠ R (ACD)+= ACDB = R, X = ACD, i =1 3) i, как видим, возросло, значит опять 2) 2) (CD)+= CD ≠ R (AD)+= ADB ≠ R (AC)+= ACBD = R, X 2= AC, i =2 3) i, как видим, возросло, значит опять 2) 2) C += C ≠ R A += AB ≠ R 3) i не возросло, значит X = X 2= AC - это ключ. Причём, можно показать, что он единственный. Теперь предполагаем тройку:
Проверям три условия для неё: 1) X → Y, так как AC → A по 1 аксиоме Армстронга; 2) Y → H, A → B по условию; 3) Y ↛ X, A ↛ AC A += AB, AC ⊈ A + Таким образом, найдена тройка, для которой выполняются все три условия, а значит отношение не находится в 3НФ.
Пример 2 Декомпозируем эту схему отношения R на две схему отношений. R =(A, B, C, D) F =(A → B, AC → D) ρ =(AB, ACD)=(R 1, R 2) Если R 1 и R 2 находятся в 3НФ, то значит всё ρ будет в 3НФ. Сначала покажем 3НФ у R 1=(AB), F =(A → B): · X = A - выберем ключом · Y, X → Y, Y ↛ X Y = B, A → B, B ↛ A · невозможно подобрать непервичный атрибут H ∉ Y, потому что непервичным может быть только B. Таким образом, нельзя подобрать необходимую тройку. Значит, R 1 находится в 3НФ. Теперь покажем 3НФ у R 2=(ACD), F =(AC → D): · X = AC - выберем ключом · Y, X → Y, Y ↛ X а) A - что-то как-то не выполняется; б) C - что-то как-то не выполняется; в) D - что-то как-то не выполняется; г) AD - что-то как-то не выполняется; д) CD - что-то как-то не выполняется. · H ∉ Y, H = D а) Y = A, Y ↛ H б) Y = C, Y ↛ H в-д) H ∈ Y Не удалось подобрать нужную тройку, так что R 2 тоже находится в 3НФ.
|
||||||
Последнее изменение этой страницы: 2021-04-12; просмотров: 73; Нарушение авторского права страницы; Мы поможем в написании вашей работы! infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 3.146.105.137 (0.021 с.) |