Итак, заключительная часть моей дипломной работы, посвященной реля- ционным базам данных... Последняя редакторская правка - 1996 год. Из-за очень сильного противодействия моя работа по оформлению по- лученных результатов была прекращена... Мне пришлось делать тяжелый выбор: или, несмотря ни на что, продол- жать вести исследования, не имея впереди АБСОЛЮТНО никаких перспек- тив; или продолжить заниматься ИСКЛЮЧИТЕЛЬНО ПРАКТИЧЕСКОЙ РЕАЛИЗА- ЦИЕЙ УЖЕ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ. Я выбрал последнее. А теория реляционных баз данных оказалась исключительно подходящим объектом-полигоном для проверки практической пригодности моей кон- цепции ИНФОРМАЦИОННЫХ ОБОБЩЕНИЙ. И это - ПЕРВЫЙ КИТ, на котором ба- зируется Партнерская Система ЗОРАН (ее практическая реализация). Ну, ВТОРОЙ КИТ - это и так понятно: концепция искусственного интел- лекта... В общем, используя информационные обобщения, мне удалось легко и просто доработать стандартную теорию реляционных баз данных, соз- дать на ее основе новую методику нормализации отношений, реализо- вать эту методику в виде конкретного алгоритма для макета АРМА ''НОРМАЛИЗАТОР''. Первая половина этой части моей работы, опять-таки, компилятивная. Опять стоим ''на плечах гигантов''! Зато вторая ее часть - это уже ПРАКТИЧЕСКОЕ применение моей концепции ИНФОРМАЦИОННЫХ ОБОЩЕНИЙ. Итак, вот она, важнейшая ступенька, ведущая к созданию Партнерской Системы ЗОРАН! ___________________________________________________________________ 1). Основы реляционной модели баз данных ( БД ). ________________________________________________ При любом методе проектирования моделей предметной области осно- вой является кодирование понятий и отношений между понятиями в модели данных.Реляционная модель данных берет в основу кодирования понятие отношения.Эта модель наиболее абстрактная,она не различает понятия объекта и связи между объектами. (1) Достоинства реляционной модели : независимость от представления данных в памяти,простота и возможность формализации задач,связанных с созданием базы данных.К числу важнейших из них относится логическое проектирование БД. (2) Реляционная модель наиболее проста и однотипна,но при ее реали- зации на физическую память в общем случае требуется больше памяти,чем на иерархическую или сетевую модель.Кроме того,в случаях модификации хранимых данных,для нее также характерны аномалии по обработке дан- ных.Эти аномалии можно снизить до минимума,если набор отношений,опи- сывающий предметную область,привести,как минимум,к третьей усиленной ( бойс-коддовской ) нормальной форме. (1) Однако,среди всех моделей данных только одна стандартизована по множеству операций ( к этим операциям относятся операции выбора дан- и операции корректировки данных ) - это реляционная модель. КОПЕЙКИН ОТНОШЕНИЕ _________ Пусть имеется n множеств { D1,D2,...,Dn },тогда R - есть ОТНОШЕНИЕ на данном множестве,если оно представимо в виде < d1,d2,...,dn >,где di принадлежит Di. Множество элементов,составляющих R,называются КОРТЕЖАМИ.Факти- чески,отношение R есть подмножество декартова произведения. R входит составной частью или совпадает с D1*D2*...*Dn,где * означает операцию прямого произведения.Исходный элемент из множества D1...Dn,называется ДОМЕНОМ.Каждый домен - это область определения от- ношения R,при этом элементы доменов ЭЛЕМЕНТАРНЫ,то есть сами по себе они не являются множествами или,другими словами,являются неделимыми идентификаторами информационных объектов или уникальных чисел,их изо- бражающих. (1) Отношение - это множество,а все элементы любого множества должны быть попарно различимы,поэтому в отношении не может быть двух одина- ковых кортежей. (1) Количество элементов в кортеже называется СТЕПЕНЬЮ отношения ( отношения бывают унарные,бинарные и n-арные ). Количество кортежей в отношении определяют МОЩНОСТЬ отношения. ПРИМЕР : Пусть имеется два множества : F={ F1,F2 } - множество факультетов института и G={G1,G2,G3 } - Множество групп,тогда Декартово произведение - F*G ,а отношение R,например,- F1G2 F1G1 F2G2 F1G2 F1G3 F2G1 F2G2 F2G3 Как видно из примера,отношение R является подмножеством декарто- ва произведения. Имя отношения ( идентификатор ) и совокупность имен атрибутов составляют СХЕМУ ОТНОШЕНИЯ,например, ГРУППА(шифр группы,студент).Кор- тежи отношения могут со временем меняться,что будет соответствовать определенному событию в отображаемой ПРЕДМЕТНОЙ ОБЛАСТИ ( предметная область - это реальный мир,который посредством моделей отображается в памяти ЭВМ ).Именно это отличает понятие отношения реляционной модели от строгого математического определения отношения,в котором говорит- ся,что отношение определено и со временем не изменяется ; если же ка- кой-нибудь кортеж изменился,то это будет другое отношение. Совокупность схем отношений составляет СХЕМУ БД.Состояние схемы БД - это сама БД. ФУНКЦИОНАЛЬНЫЕ ЗАВИСИМОСТИ В ОТНОШЕНИЯХ. ___________________________________________ Реляционная модель учитывает ограничения,накладываемые семанти- кой предметной области на используемые данные.Одним из таких ограни- чений,существующих в предметной области,является понятие функциональ- ной зависимости,которое поддается строгой формализации и на основании которого можно правильно спроектировать схему БД.Известно,что реляци- онная модель БД представляет собой совокупность схем отношений,описы- вающих некоторую предметную область.С точки зрения реляционного под- хода любая предметная область может быть описана с помощью только од- ного строительного блока - отношения,которое покрывает различные по- нятия инфологической модели. Такие понятия,как объект и связь между объектами,представлены в реляционной модели одним типовым блоком отношений.Естественно,что та- кое отношение будет иметь какие-то внутренние ограничения,учитываю- особенности моделируемой предметной области. (1) Определение функциональной зависимости. Пусть Wr - множество всех атрибутов,входящих в отношение R.Тогда " множество Y,принадлежащее Wr,функционально зависит от множества X, принадлежащего Wr,если в любой момент времени для любых элементов r1, r2,принадлежащих R,из r1[X]=r2[X] следует r1[Y]=r2[Y].Функциональная зависимость Y от X обозначается через R.X -> R.Y или просто X -> Y при условии,что отношение R фиксировано. ( Здесь R[X] - проекция от- ношения R на X ) " (3) Определение функциональной зависимости можно сформулировать и по-другому.Функциональной зависимостью набора атрибутов B отношения R от набора атрибутов A того же отношения называется соотношение эле- ментов проекций R[A] и R[B],обозначаемое R.A -> R.B,при котором в каждый момент времени любому элементу проекции R[A] соответствует только один элемент проекции R[B],входящий вместе с ним в какой-ни- будь кортеж отношения R. Наличие функциональной зависимости является свойством схем,а не того или иного экземпляра отношения и отражает семантику моделируемо- го в БД объекта.Поэтому функциональные зависимости - важная разновид- ность информационных инвариантов схемы БД,иначе называемых ограниче- ниями целостности.Информационные инварианты представляют собой преди- каты,которые должны принимать значения " истина " на любом экземпля- ре БД. (2) ПОЛНАЯ ФУНКЦИОНАЛЬНАЯ ЗАВИСИМОСТЬ. ____________________________________ Множество Y,принадлежащее Wr,функционально полно зависит от X, принадлежащего Wr,если X -> Y и никакое собственное подмножество X' множества X этим свойством не обладает.Полная функциональная зависи- мость Y от X называется также элементарной функциональной зависимос- тью. (3) Или : пусть дана функциональная зависимость A1,A2,A3,...,An -> B, тогда зависимость называется полной,если ни один из атрибутов,стоя- щих в левой части функциональной зависимости,не может быть удален без разрушения свойства функциональной зависимости. (1) ДЕТЕРМИНАНТА. _____________ Договоримся называть некоторый атрибут ( возможно составной ),от которого какой-либо другой атрибут зависит функционально полно,детер- минантой. (4) ВОЗМОЖНЫЙ КЛЮЧ. ________________ Набор K атрибутов отношения R называется возможным ключом отно- шения R,если верно,что 1) Каждый атрибут отношения R функционально зависит от К 2) Ни один атрибут из набора K не может быть удален без нарушения свойства 1). Обозначим Ur полный набор атрибутов отношения R.Тогда определе- ние возможного ключа K отношения R может быть записано следующим об- разом : если для любого A,принадлежащего Ur,K -> A ( 1 ) и для любого K',принадлежащего K,существует B,принадлежащее Ur,причем K' не определяет функционально B, ( 2 ) то K - возможный ключ. Условие ( 1 ) эквивалентно K -> Ur , ( 3 ), (2) то есть возможный ключ однозначно идентифицирует кортежи отношения. Или,другими словами,множество K называют возможным ключом струк- туры FD(w),если w функционально полно зависит от K. (3) СТРУКТУРА FD(w). _________________ Для любого конечного множества будем говорить,что на w задана структура функциональных зависимостей,если на булеане E(w) задано би- нарное отношение f,удовлетворяющее условиям * и ** * Если Y принадлежит X или совпадает с X,то X -> Y ** Если X -> Y и YZ -> U,то XZ -> U Структура функциональных зависимостей на w будет обозначаться FD(w). (3) СВЕРХКЛЮЧ. __________ Если X содержит возможный ключ K,то X называется сверхключом. Множество X сверхключ тогда и только тогда,когда X -> W. (3) Множество M такое,что в него входит множество K,где K - возмож- ный ключ,называется сверхключом. (2) ОПРЕДЕЛЕНИЯ,ВЫТЕКАЮЩИЕ ИЗ ПОНЯТИЯ ВОЗМОЖНОГО КЛЮЧА. _______________________________________________________ Возможных ключей может быть несколько,тогда они образуют множес- тво.Из этого множества выбирается один элемент в качестве кандидата на ГЛАВНЫЙ ключ.Все атрибуты отношения с помощью понятия возможного ключа разбиваются на ПЕРВИЧНЫЕ ( если они входят в какой-либо возмож- ный ключ ) и НЕПЕРВИЧНЫЕ ( в противном случае ). После введения понятия функциональной зависимости и ключа отно- шения дополняется понятие СХЕМЫ ОТНОШЕНИЯ.Схема отношения состоит из имени отношения,множества имен атрибутов,среди которых выделено под- множество,составляющее главный ключ,и множества функциональных зави- симостей,определенных на множестве всех имен атрибутов. Тогда СХЕМА БАЗЫ - это набор схем отношений и набор функциональ- ных зависимостей,объединяющий все функциональные зависимости всех от- ношений. (1) АКСИОМАТИКА ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ. __________________________________________ Администратор базы обычно выделяет только часть функциональных зависимостей,которые в дальнейшем будем обозначать через F.Через F+ будем обозначать полное множество функциональных зависимостей.В общем случае F принадлежит F+.F+ назовем замыканием.Если известно F и к не- му применить специальные правила,называемые аксиомами вывода,то F+ может быть построено с помощью правил логического вывода.Пусть r - отношение со схемой R и заданы атрибуты X,Y,W,Z,причем X принадлежит R Y принадлежит R Z принадлежит R W принадлежит R,тогда справедливы следующие аксиомы вывода: 1)ФЗ1(рефлексивность) : если Y совпадает с X либо принадлежит X, то X -> Y. 2)ФЗ2(присоединение) : если Z совпадает с W либо принадлежит W, то XW -> YZ. 3)ФЗ3(транзитивность) : если X -> Y и Y -> Z,то X -> Z. Здесь X,Y,Z и W - подмножества множества атрибутов A1,...,An.Это полный набор правил,то есть он позволяет вывести на основе F все дос- товерные зависимости.Вместе с тем удобно ввести дополнительные прави- ла - следствия ФЗ1,ФЗ2,ФЗ3. 4)ФЗ4(псевдотранзитивность) : если X -> Y и YW -> Z,то XW -> Z. 5)ФЗ5(объединение) : если X -> Y и X -> Z,то X -> YZ. 6)ФЗ6(декомпозиция) : если X -> YZ,то X -> Y и X -> Z. Замыканием F+ множества функциональных зависимостей F называет- ся множество функциональных зависимостей,выводимых в F.F+ может быть получено с помощью правил ФЗ1,ФЗ2,ФЗ3.Приведем возможный алгоритм вы- вода : 1) Все функциональные зависимости,входящие в F,входят также в F+. 2) Для всех подмножеств X и Y множества атрибутов A1,...,An,если Y совпадает с X либо принадлежит X,то X -> Y принадлежит F+. 3) Для всех подмножеств X,Y и Z множества атрибутов A1,...,An, если X -> Y и Y -> Z принадлежат F+,то X -> Z принадлежит F+. 4) Для всех подмножеств X,Y и Z множества атрибутов A1,...,An, если X -> Y и X -> Z принадлежат F+,то X -> YZ также принад- лежит F+ 5) Никаких других функциональных зависимостей в F+ не содержит- ся. Даже при небольшой мощности F число функциональных зависимостей в F+ может быть весьма велико,в силу чего вычисление F+ - весьма вре- мяемкая процедура. (5) ВОЗМОЖНЫЕ ВЗАИМОСВЯЗИ ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ В ОТНОШЕНИЯХ. ____________________________________________________________________ Рассмотрим важные частные случаи функциональных зависимостей,на которые будем ссылаться следующим образом. F1.1 - неполная функциональная зависимость набора непервичных атрибутов от возможного ключа. F1.2 - неполная функциональная зависимость набора первичных ат- рибутов от несодержащего его возможного ключа ( заметим, что первичные атрибуты всегда полно зависят от содержаще- го их возможного ключа,так как любые два подмножества ключа функционально независимы друг от друга ). F2.1 - транзитивная функциональная зависимость ( см.аксиому тран- зитивности ) непервичных атрибутов от возможного ключа. F2.2 - транзитивная функциональная зависимость набора первичных атрибутов от несодержащего его возможного ключа. F2.3 - транзитивная функциональная зависимость набора первичных атрибутов от содержащего его возможного ключа.Здесь под набором первичных атрибутов понимается совокупность атри- бутов,входящая в некоторый возможный ключ отношения. Взаимосвязи между названными типами функциональных зависимостей устанавливает следующая ТЕОРЕМА 2 : Транзитивная зависимость набора первичных атрибутов от содержащего его возможного ключа ( F2.3 ) вле- чет наличие либо неполной ( F1.2 ),либо транзитивной зависимости это- го набора ( F2.2 ) от несодержащего его возможного ключа и наоборот. Зависимиости F1.1,F1.2,F2.1 и F2.2 несводимы друг к другу. МНОГОЗНАЧНЫЕ ЗАВИСИМОСТИ. __________________________ Пусть R(U) - отношение с совокупностью атрибутов U,X и Y - под- множества U,при этом X и Y могут пересекаться.Определим множество YR(r)={y/существует r,принадлежащий R,r[x]=x,r[y]=y}. Пусть Z=U/XY,тогда будем говорить,что в R имеет место многознач- ная зависимость g : X -> -> Y,если для любого значения xz совокупнос- ти атрибутов XZ верно YR(xz)=YR(x).Другими словами,совокупность зна- чений атрибута Y,которая появляется в кортежах отношения R с заданным значением x атрибута X,появляется с каждой комбинацией значений x и z,принадлежащего Z,xz принадлежит R[xz].Таким образом,множество зна- чений Y для заданного x не зависит в данном случае от значений Z,по- являющихся вместе с X.Будем также говорить,что Y зависит многозначно от X. Непосредственно из определения следует следующее ПРЕДЛОЖЕНИЕ 2 : для любых X и Y,таких,что XY совпадают с Ur либо принадлежат Ur,мно- гозначная зависимость X -> -> Y имеет место в R тогда и только тогда, когда в R имеет место X -> -> Y-X. (2) АКСИОМАТИКА МНОГОЗНАЧНЫХ ЗАВИСИСОСТЕЙ. ________________________________________ Многозначные зависимости,так же как и функциональные,играют важ- ную роль при проектировании логической схемы БД.Поэтому большой инте- рес представляет задача построения полной системы аксиом для структу- ры многозначных зависимостей.Эту задачу решили Биэри,Фэджин и Ховард. При этом каждая из предложенных аксиом,за исключением одной,является аналогом соответствующей аксиомы Армстронга ( см.аксиоматику функцио- нальных зависимостей ). Пусть X,Y,Z - подмножества из совокупности атрибутов Ur отноше- ния R.Тогда система аксиом Биэри,Фэджина и Ховарда включает следую- щие аксиомы. М0) если XYZ=Ur,а пересечение Y и Z совпадает с X либо принадле- жит X,то X -> -> Y тогда и только тогда,когда X -> -> Z (до- полнение ). М1) если Y совпадает с X либо Y принадлежит X,то X -> -> Y ( ре- флексивность ). М2) если X -> -> Y и W совпадает с Z либо W принадлежит Z,то XZ -> -> YW ( продолжение ). М3) если X -> -> Y и Y -> -> Z,то X -> -> Z-Y ( транзитивность ) Следующие свойства выводимы из М0-М3 : М4) если X -> -> Y и YW -> -> Z,то XW -> -> Z-YW ( псевдотранзи- тивность ). М5) если X -> -> Y и X -> -> Z,то X -> -> YZ ( аддитивность ). М6) если X -> -> Y1 и X -> -> Y2,то X -> -> Y1 пересекается с Y2,X -> -> Y1-Y2,X -> -> Y2-Y1 ( декомпозиция ). Заметим,что М0 не имеет аналога среди аксиом Армстронга и явля- ется единственным правилом,для которого результат применения зависит от Ur в целом.Аксиомы М3,М4 и М6 более ограничены по сравнению с со- ответствующими аксиомами Армстронга.Можно показать,что М4 является М2 и М3,а М5 - следствием М0,М2 и М3. Мендельсон исследовал роль аксиомы М0 и показал,что М5 не может быть выведена без использования М0,в то время как М6 выводима из М1- М3.Он также построил все допустимые минимальные подмножества М0-М6, являющиеся полными наборами аксиом.Таких подмножеств всего два : { М0,М1,М3 } и { М0,М1,М4 } Аксиома М2 выводима из М0 и М1.Набор { М0,М1,М3 } можно считать в не- котором смысле более минимальным,так как М4 является обобщением М3. Биэри,Фэджин и Ховард предложили также набор аксиом для вывода функциональных и многозначных зависимостей из заданного множества многозначных и функциональных зависимостей. ФМ1) если X -> Y ,то X -> -> Y. ФМ2) если X -> -> Z и Y -> Z',где Z' совпадает с Z либо принад- лежит Z,причем Y и Z не пересекаются,то X -> Z'. Из ФМ1 и ФМ2 выводимо также следующее правило : ФМ3) если X -> -> Y и XY -> Z,то X -> Z-Y. (2) ТРИВИАЛЬНАЯ многозначная зависимость - это зависимость вида X -> -> Y,Y -> -> X в R(X,Y). (5) НОРМАЛЬНЫЕ ФОРМЫ ОТНОШЕНИЙ. _____________________________ Нормальные формы отношений были предложены прежде всего для по- давления избыточности данных в базе и устранения побочных эффектов при модификации хранимых данных.Основой для построения нормализован- ной реляционной модели БД является отношение в ПЕРВОЙ НОРМАЛЬНОЙ ФОР- МЕ ( 1НФ ),которая требует,чтобы элементы доменов отношения не явля- лись множествами.Это единственное требование,накладываемое на отноше- ние в 1НФ и наличие функциональных зависимостей в отношении не сказы- вается на структуре отношения в 1НФ. Отношение R находится во ВТОРОЙ НОРМАЛЬНОЙ ФОРМЕ ( 2НФ ),если каждый непервичный атрибут функционально полно зависит от каждого во- зможного ключа.При этом отношение должно также находиться в 1НФ. Для определения,находится ли отношение в 2НФ необходимо : 1) выявить все возможные ключи. 2) определить все непервичные атрибуты. 3) выявить все неполные функциональные зависимости. Отношение R находится в ТРЕТЬЕЙ НОРМАЛЬНОЙ ФОРМЕ,если оно нахо- дится в 2НФ и каждый непервичный атрибут нетранзитивно зависит от ка- ждого возможного ключа,то есть здесь должны отсутствовать транзитив- ные зависимости между непервичными атрибутами.Третью нормальную форму будем обозначать далее 3НФ. Если же запретить функциональные зависимости между первичными атрибутами в 3НФ,то отношение будет находиться в ТРЕТЬЕЙ УСИЛЕННОЙ НОРМАЛЬНОЙ ФОРМЕ ( 3УНФ ) или так называемой БОЙС-КОДДОВСКОЙ НОРМАЛЬ- НОЙ ФОРМЕ ( БКНФ ). (1) Несколько другую трактовку нормальных форм отношений дает Дри- бас.Он предлагает определять различные типы нормальных форм отношений на основе функциональных зависимостей вида F1.1,F1.2,F2.1 и F2.2,а не только на основе функциональных зависимостей вида F1.1 и F2.1,как это было показано выше.Нормальные формы отношений связаны с введенными зависимостями следующим образом : Нормальные формы Отсутствующие в отношении отношения зависимости ВТОРАЯ F1.1 УСИЛЕННАЯ ВТОРАЯ F1.1,F1.2 ТРЕТЬЯ F1.1,F2.1 УСИЛЕННАЯ ТРЕТЬЯ F1.1,F1.2,F2.1,F2.2 Однако Дейт в своих работах подчеркивает,что на самом деле пер- вая и вторая нормальные формы в действительности не так уж и важны ; и,в общем-то,ими в основном пользуются лишь в качестве промежуточных состояний при приведении отношений к третьей и четвертой нормальным формам.Далее автор говорит,что можно дать определение БКНФ,не ссыла- ясь при этом на первую или вторую нормальные формы и на понятие пол- ной и транзитивной зависимостей.Приведем это определение : нормализо- ванное отношение R находится в БКНФ,если каждая детерминанта является возможным ключом.Это определение будет использовано в дальнейшем при построении алгоритма по нормализации отношений.(4) Перейдем теперь к определению ЧЕТВЕРТОЙ НОРМАЛЬНОЙ ФОРМЫ ( 4НФ ). Предложение 4 : Если отношение R находится в 4НФ,то оно также нахо- дится в БКНФ. Введем понятие СЛАБОЙ ЧЕТВЕРТОЙ НОРМАЛЬНОЙ ФОРМЫ ( СЧНФ ).Будем говорить,что отношение R находится в СЧНФ,если в нем все НЕТРИВИАЛЬ- НЫЕ многозначные зависимости являются функциональными.Очевидно сле- дующее : Предложение 5.Отношение R находится в 4НФ тогда и только тогда, когда оно находится в БКНФ и СЧНФ.(2) Отношение находится в 4НФ,если все нетривиальные многозначные зависимости есть зависимости от ключа.(5) МЕТОДЫ И СПОСОБЫ РЕШЕНИЯ ЗАДАЧИ ПО НОРМАЛИЗАЦИИ ОТНОШЕНИЙ. ________________________________________________________________ ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ ПРОЕКТИРОВАНИЯ РЕЛЯЦИОННОЙ СХЕМЫ. ___________________________________________________________________ Пусть задана схема S0,содержащая схему одного отношения R, S0={ R=< U,G > }, где U - множество атрибутов отношения,G - некоторая система образую- ющих структуры функциональных или многозначных зависимостей Ur.Необ- ходимо найти эквивалентную реляционную схему Sd={ Ri=,i=1,2,...,n }, которая была бы в некотором смысле лучше схемы S0.Неформально схемы S0 и Sd эквивалентны,если они способны представлять одну и ту же ин- формацию.Следовательно,точный смысл понятия эквивалентности зависит от определения информации,представляемой схемой.Рассмотрим следующие определения эквивалентности : Определение E1.Схема Sd представляет ту же информацию,что и схе- ма S0,если эти схемы имеют одинаковые атрибуты и сохранены все зави- симости данных. Если рассматривать только функциональные зависимости,то опреде- ление E1 может быть сделано точным.Пусть G - система образующих структуры функциональных зависимостей,тогда S0 и Sd эквивалентны,по определению E1,если n n U = U Ui и G+ = ( U Gi )+ i=1 i=1 Таким образом,структура функциональных зависимостей отношения R поро- ждается структурами функциональных зависимостей проекций Ri. В определении Е1 существенным образом были использованы предпо- ложение о существовании универсального множества и свойства прямой и обратной проективности функциональной зависимости.Так как многознач- ные зависимости не обладают свойством обратной проективности,то воз- можность соответствующего обобщения E1 неясна. Определение E2.Схема Sd представляет ту же информацию,что и схе- ма S0,если n U = U UI i=1 и база со схемой Sd содержит те же данные, что и база со схемой S0. Пусть R' - экземпляр отношения со схемой R и соответствующим множеством экземпляров отношений базы со схемой Sd является : { Ri' = R[Ui],i=1,2,...,n }. Тогда определение E2 формализуется с помощью понятия соединения без потерь,при котором R'=R1'*R2'*...*Rn'.Будем говорить,что Sd обладает свойством соединимости без потерь,если для любого экземпляра R' схемы R верно n R'= *R'[Ui] i=1. Определение E3.Схема S0 представляет ту же информацию,что и схе- Sd тогда и только тогда,когда существует взаимно-однозначное соответ- ствие между S0 и Sd. Определение E3,по существу,является комбинацией определений E1 и E2,которые не эквивалентны друг другу. АЛГОРИТМЫ ПРОЕКТИРОВАНИЯ РЕЛЯЦИОННОЙ СХЕМЫ БАЗЫ ДАННЫХ. ____________________________________________________________ Различия между алгоритмами во многом обусловлены различным под- ходом к определению эквивалентности схем и к выбору критериев качест- ва схемы. Характеристики алгоритмов проектирования реляционных схем. __________________________________________________________ __________________________________________________________________ Авторы алго- Фэджин Делобель- Бернштейн Ислур Неклюдова- ритма Кейси Цаленко __________________________________________________________________ Зависимости данных на входе алго- мз фз фз фз фз ритма. __________________________________________________________________ Эквивалент- E3= E3= ность схем E2 = (E1,E2) E1 E1 =(E1,E2) Sd и S0 __________________________________________________________________ Нормализо- ванная фор- 4НФ 3НФ 3НФ 3НФ 3НФ ма схемы Sd __________________________________________________________________ Количествен- ная оптима- льность схе- Н Н Н Н О мы Sd __________________________________________________________________ Вычислитель- ная слож- 2 2 ность алго- NP NP 0(/G/ ) 0(/G/ ) NP ритма __________________________________________________________________ Обозначения : мз - многозначные зависимости,фз - функциональные зависимости;NP - алгоритм включает решение NP-полной задачи;Н - схема Sd-неоптимальна;О - схема SD-оптимальна. ОГРАНИЧЕНИЯ В СПОСОБАХ РЕАЛИЗАЦИИ И НЕДОСТАТКИ. ____________________________________________________ Основным преимуществом процедуры Фэджина является высокая сте- пень разделения представления связей.Кроме того,она позволяет приво- дить отношения к4НФ.Процедура Фэджина имеет и ряд недостатков.Так как декомпозиции не уникальны,то в общем случае неясно,как получать схе- мы,имеющие " естественный " вид.Кроме того,зависимости в результиру- ющей схеме могут весьма хитроумно зависеть от исходной системы обра- зующих одной и той же структуры зависимостей.Наконец,процедура Фэд- жина алгоритмически исключительно неэффективна - ведь выяснение воп- роса " Находится ли заданная реляционная схема в 4НФ ? " является NP-полной задачей.А в процедуре Фэджина этот вопрос приходится решать на каждом этапе декомпозиции.Также процедура Фэджина является коли- чественно неоптимальной. Алгоритм Делобеля-Кейси приводит реляционную схему к 3НФ,но по- лученная схема не является количественно оптимальной.Так как этот ал- горитм включает на первом шаге задачу нахождения возможных ключей,то он имеет неполиномиальную оценку сложности. Алгоритм Бернштейна дает схему Sd,эквивалентную схеме S0 по оп- ределению E1,но не по определению E2.Таким образом,алгоритм Бернштей- на,сохраняя базис,не учитывает всей структуры функциональных зависи- мостей исходного отношения.Результирующая схема в общем случае не яв- ляется количественно оптимальной. Алгоритм Ислура близок по конструкции алгоритму Бернштейна,но отличается большей логической простотой. В алгоритме Неклюдовой-Цаленко устранены отмеченные выше недос- татки алгоритмов Бернштейна и Делобеля-Кейси.Вотличие от всех рас- смотренных алгоритмов алгоритм Неклюдовой-Цаленко ( ниже для краткос- ти НЦ-алгоритм ) дает количественно оптимальную схему Sd,эквивалент- ную схеме S0 как по определению E1,так и по E2,получая тем самым ко- личественно оптимальное синтаксическое разложение.Так как в НЦ-алго- ритме на шаге 1 требуется решить NP-полную задачу нахождения ключей отношения,то и НЦ-алгоритм в целом имеет неполиномиальную структуру. Ни один из рассмотренных алгоритмов не имеет преимущества над остальными по всем характеристикам.Принципиальная невозможность пост- роения " абсолютно лучшего " алгоритма следует из существования таких схем S0,для которых отсутствует синтаксическое разложение в 4НФ.Таким образом,выбор алгоритма определяется " весом " той или иной характе- ристики в конкретной ситуации.С одной стороны,стремление к 4НФ за счет отказа от сохранения базиса функциональных зависимостей не пред- ставляется целесообразным.С другой стороны,из-за аномалий обновления отношений,не находящихся в 4НФ,надо стремиться к схемам с наиболее " сильной " нормальной формой.В этом смысле имеет преимущество алго- ритм Бернштейна.Он дает наиболее близкие к БКНФ схемы,поскольку поз- воляет устранить транзитивные зависимости первичных атрибутов от не- содержащих их ключей.В то же время НЦ-алгоритм,который дает количест- венно оптимальную схему,эти зависимости сохраняет. Так как алгоритмы проектирования реляционной схемы применяются на начальном этапе создания банка данных,то эффективность алгоритмов отступает на второй план,однако полностью пренебрегать ею также нель- зя.В реальной ситуации проектирование реляционной схемы будет проис- ходить при активном участии человека.Поэтому при создании диалоговых схем проектирования БД медленная работа алгоритма может оказаться серьезным недостатком. (2) ТРЕБОВАНИЯ К РАЗРАБАТЫВАЕМОМУ АЛГОРИТМУ. ___________________________________________ За точку отсчета при разработке алгоритма при приведении отноше- ний к той или иной нормальной форме целесообразно взять таблицу хара- ктеристик алгоритмов,которая показывает,что уже было сделано в облас- ти нормализации отношений,процедуру Фэджина,поскольку она единствен- ная,приводящая отношение к 4НФ,а также алгоритм построения замыкания для заданных структур функциональных и многозначных зависимостей.Те- перь можно будет сформулировать требования к разрабатываемому алго- ритму. Из анализа таблицы характеристик алгоритмов видно следующее : 1) Разрабатываемый алгоритм должен принимать на входе функцио- нальные зависимости. 2) Разрабатываемый алгоритм должен принимать на входе многознач- ные зависимости. 3) Разрабатываемый алгоритм должен принимать на входе совокуп- ность функциональных и многозначных зависимостей. 4) Разрабатываемый алгоритм должен приводить заданное отношение к 4НФ. 5) Разрабатываемый алгоритм желательно сделать более оптималь- ным,чем процедура Фэджина ( вопрос оптимальности в дальней- шем будет подробно рассмотрен ). 6) Желательно,чтобы рассматриваемый алгоритм был как можно более простым ( то есть не включал бы в себя решение NP-полной за- дачи ),а для этого нужно : a) Перед началом работы основной части алгоритма выяснить,на- ходится ли отношение в 4НФ.Причем эту задачу придется ре- шать,как и в процедуре Фэджина,на каждом этапе декомпози- ции.Однако выше было сказано,что данная задача являеся NP- полной,если ее решать традиционными методами.Следователь- но,придется искать принципиально новое решение ( если только оно вообще возможно ). b) Поскольку поиск возможных ключей заданного отношения тоже является NP-полной задачей,желательно найти такой способ разложения,который бы не требовал поиска всех возможных ключей отношения,либо же сконструировать такой алгоритм поиска возможных ключей ( да и сверхключей тоже ),который был бы значительно проще всех существующих.Кроме того,в ходе разложения заданного отношения неоднократно придется решать вопрос,является ли та или иная функциональная или многозначная зависимость ключевой ; поэтому решение данно- го вопроса должно находиться за одну-три машинные опера- ции. с) Провести тщательную классификацию функциональных и многоз- начных зависимостей,с тем чтобы рассматривать только та- кие зависимости,которые нам будут необходимы для декомпо- зиции,то есть необходимо каким-то образом рассматривать не все замыкание,которое может быть получено при использова- нии аксиом вывода функциональных зависимостей,а только его некоторую часть. 7) Из рассмотренных выше требований и пожеланий видно,что при их реализации получится алгоритм,который можно сделать основой для программной системы,осуществляющей разложение отношений в 4НФ в диалоговом режиме,причем полученная процедура будет ра- ботать гораздо быстрее процедуры Фэджина. НОВЫЕ ОПРЕДЕЛЕНИЯ И ДЕЙСТВИЯ. ________________________________ КЛАССИФИКАЦИЯ ФУНКЦИОНАЛЬНЫХ И МНОГОЗНАЧНЫХ ЗАВИСИМОСТЕЙ. _____________________________________________________________ Введем теперь несколько новых определений и действий,вытекающих из аксиом вывода для функциональных и многозначных зависимостей,также произведем их классификацию. ЯВНОЙ ФУНКЦИОНАЛЬНОЙ ЗАВИСИМОСТЬЮ называется такая функциональ- ная зависимость,которая в своей правой части содержит список всех тех имен атрибутов,которые входят и в левую часть заданной функциональ- ной зависимости нормализуемого отношения. ПРИМЕР : Задано отношение R(X1,X2,X3,X4,X5,X6,X7,X8,X9,X10),причем X1 X2 -> X3 X4 X5 X6 X7 X1 X2 -> X2 X3 X4 X5 X6 X7 X1 X2 -> X1 X2 X3 X4 X5 X6 X7 Только одна из вышеприведенных функциональных зависимостей,а именно : X1 X2 -> X1 X2 X3 X4 X5 X6 X7 является явной,поскольку в ее правой части присутствуют имена всех тех атриюутов,которые входят в левую часть данной функциональной зависимости.Все остальные функциональные зависимости - НЕЯВНЫЕ. ЯВНЫМ КЛЮЧОМ называется такой возможный ключ,который в своей правой части содержит список имен ВСЕХ атрибутов нормализуемого отно- шения. ПРИМЕР : Задано отношение R(X1,X2,X3,X4,X5,X6,X7) со следующими ключами X1 X2 -> X3 X4 X5 X6 X7 X1 X2 -> X2 X3 X4 X5 X6 X7 X1 X2 -> X1 X2 X3 X4 X5 X6 X7 Все эти три КЛЮЧЕВЫЕ функциональные зависимости присутствуют в замыка- нии.Они построены с помощью соответствующих аксиом,но только одна из них,а именно : X1 X2 -> X1 X2 X3 X4 X5 X6 X7 является явным ключом, поскольку в ее правой части присутствуют имена всех атрибутов норма- лизуемого отношения.Остальные ключи - НЕЯВНЫЕ. Определение ЯВНОГО СВЕРХКЛЮЧА совершенно аналогичное.Явным сверх- ключом называется такой сверхключ,который в своей правой части содер- жит список имен всех атрибутов нормализуемого отношения. Явный ключ,также как и явный свехключ,- это частный случай явной функциональной зависимости. ПРАВИЛЬНАЯ ФУНКЦИОНАЛЬНАЯ ЗАВИСИМОСТЬ - это такая зависимость, правая часть которой НЕ СОДЕРЖИТ НИ ОДНОГО ИМЕНИ АТРИБУТА из тех ат- рибутов,которые находятся в левой части. ПРИМЕР : Задано отношение R(X1,X2,X3,X4,X5,X6,X7,X8,X9,X10),причем X1 X2 -> X3 X4 X5 X6 X7 X1 X2 -> X2 X3 X4 X5 X6 X7 X1 X2 -> X1 X2 X3 X4 X5 X6 X7 Только одна из вышеприведенных функциональных зависимостей,а именно : X1 X2 -> X3 X4 X5 X6 X7 является правильной,поскольку в ее правой части отсутствуют имена всех тех атрибутов,которые входят в левую часть данной функциональной зависимости.Все остальные функциональные зависимости - НЕПРАВИЛЬНЫЕ. ПРАВИЛЬНЫМ КЛЮЧОМ называется такой возможный ключ,правая часть которого НЕ СОДЕРЖИТ НИ ОДНОГО ИМЕНИ АТРИБУТА из тех ат- рибутов,которые находятся в левой части. ПРИМЕР : Задано отношение R(X1,X2,X3,X4,X5,X6,X7) со следующими ключами X1 X2 -> X3 X4 X5 X6 X7 X1 X2 -> X2 X3 X4 X5 X6 X7 X1 X2 -> X1 X2 X3 X4 X5 X6 X7 Только одна из вышеприведенных функциональных зависимостей,а именно : X1 X2 -> X3 X4 X5 X6 X7 является правильным ключом,поскольку в ее пра- вой части отсутствуют имена всех тех атрибутов,которые входят в левую часть данной функциональной зависимости.Все остальные функциональные зависимости - НЕПРАВИЛЬНЫЕ КЛЮЧИ. Определение ПРАВИЛЬНОГО СВЕРХКЛЮЧА совершенно аналогичное.Пра- вильным сверхключом называется такой сверхключ,у которого в правой части отсутствуют имена всех тех атрибутов,которые входят в его левую часть. Правильный ключ,также как и правильный сверхключ,- это частный случай правильной функциональной зависимости. Правильный ключ легко может быть получен из явного.Для этого до- статочно из правой части явного ключа вычесть левую. ПРИМЕР : Задано отношение R(X1,X2,X3,X4,X5,X6,X7,X8) X1 X2 X3 -> X1 X2 X3 X4 X5 X6 X7 X8 - явный ключ, требуется из него получить правильный. Решение : {X1,X2,X3,X4,X5,X6,X7,X8}-{X1,X2,X3}={X4,X5,X6,X7,X8} Ответ : X1 X2 X3 -> X4 X5 X6 X7 X8 - правильный ключ. Аналогично из явной функциональной зависимости можно получить правильную.Если же мы из правой части явного ключа вычтем не всю ле- вую часть,а только какое-то ее подмножество,то мы получим ИДЕНТИЧНЫЙ КЛЮЧ.Аналогично,если из правой части явной функциональной зависимости вычесть подмножество левой,то получится ИДЕНТИЧНАЯ ФУНКЦИОНАЛЬНАЯ ЗА- ВИСИМОСТЬ.Таким образом,идентичный ключ - это такой неявный и непра- вильный ключ,у которого в правой части содержится какое-либо подмно- жество имен атрибутов,входящих в его левую часть.Тогда явный ключ ключ - это такой возможный ключ,у которого в правой части содержится множество ВСЕХ имен атрибутов,входящих в его левую часть.Точно также можно вывести определение идентичной функциональной зависимости.Иден- тичная функциональная зависимость - это такая неявная и неправильная функциональная зависимость,у которой в правой части содержится какое- либо подмножество имен атрибутов,входящих в ее левую часть.Тогда яв- ная функциональная зависимость - это такая функциональная зависи- мость,у которой в правой части содержится множество ВСЕХ имен атрибу- тов,входящих в левую часть данной функциональной зависимости.Совокуп- ность ВСЕХ идентичных функциональных зависимостей назовем МНОЖЕСТВОМ ИДЕНТИЧНЫХ ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ ( или просто МНОЖЕСТВОМ ИДЕН- ТИЧНЫХ ЗАВИСИМОСТЕЙ ).Совокупность правильной функциональной зависи- мости,явной функциональной зависимости и множества идентичных зависи- мостей образует ПОЛНОЕ МНОЖЕСТВО ИДЕНТИЧНЫХ ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОС- ТЕЙ ( или просто ПОЛНОЕ МНОЖЕСТВО ИДЕНТИЧНЫХ ЗАВИСИМОСТЕЙ ). Совокуп- ность всех идентичных ключей назовем МНОЖЕСТВОМ ИДЕНТИЧНЫХ КЛЮЧЕЙ.Со- вокупность правильного ключа,явного ключа и множества идентичных клю- чей образует ПОЛНОЕ МНОЖЕСТВО ИДЕНТИЧНЫХ КЛЮЧЕЙ.Ясно,что полное мно- жество идентичных зависимостей - всего-навсего одна функциональная функциональная зависимость,которая,как ползущая гусеница,то сокращает свою длину,то увеличивает ее.Покажем,что любая функциональная зависи- мость из полного множества идентичных зависимостей функционально оп- ределяет ОДНО множество имен атрибутов.Под одним множеством здесь по- нимаем совокупность ВСЕХ имен атрибутов,которые определяет любая фун- кциональная зависимость из полного множества идентичных зависимостей. ДОКАЗАТЕЛЬСТВО 1 : Задано отношение R(X1,X2,X3,...,Xm,...,Xa,...,Xe,...,Xn,...,Xz) и полное множество идентичных функциональных зависимостей P : { Xe Xf Xg ... Xm -> Xa Xb Xc ... Xn, Xe Xf Xg ... Xm -> Xe Xa Xb Xc ... Xn, Xe Xf Xg ... Xm -> Xf Xa Xb Xc ... Xn, Xe Xf Xg ... Xm -> Xg Xa Xb Xc ... Xn, Xe Xf Xg ... Xm -> Xe Xf Xa Xb Xc ... Xn, Xe Xf Xg ... Xm -> Xe Xg Xa Xb Xc ... Xn, Xe Xf Xg ... Xm -> Xf Xg Xa Xb Xc ... Xn, Xe Xf Xg ... Xm -> Xe Xf Xg Xa Xb Xc ... Xn } Здесь Xe Xf Xg ... Xm -> Xa Xb Xc ... Xn - правильная функциона- льная зависимость,а Xe Xf Xg ... Xm -> Xe Xf Xg Xa Xb Xc ... Xn - яв- ная функциональная зависимость ; остальные зависимости - идентичные. Покажем,что любая функциональная зависимость из данного множества функционально определяет то множество атрибутов,которое определяет явная функциональная зависимость. По аксиоме ФЗ1 Xe Xf Xg ... Xm функционально определяет и себя целиком и любое свое подмножество.А тогда по аксиоме ФЗ5 для любой функциональной зависимости из заданного множества получим правую часть,совпадающую с правой частью явной функциональной зависимости из вышеприведенного множества. Введем следующие действия с функциональными зависимостями.Опера- цией ПОЛНОЙ СВЕРТКИ ( по аналогии с кодами Фибоначчи ) назовем про- цесс преобразования явной функциональной зависимости в правильную.Для этого нужно из множества имен атрибутов,входящих в правую часть явной ной функциональной зависимости,вычесть множество имен атрибутов,вхо- дящих в ее левую часть. Операцией ПОЛНОЙ РАЗВЕРТКИ назовем процесс преобразования прави- льной функциональной зависимости в явную.Для этого нужно ко множеству имен атрибутов,входящих в правую часть правильной функциональной за- висимости,прибавить множество имен атрибутов,входящих в ее левую часть. Операцией НЕПОЛНОЙ или ЧАСТИЧНОЙ СВЕРТКИ назовем процесс преоб- разования функциональной зависимости из множества идентичных зависи- мостей в правильную функциональную зависимость. Операцией НЕПОЛНОЙ или ЧАСТИЧНОЙ РАЗВЕРТКИ назовем процесс преоб- разования функциональной зависимости из множества идентичных зависи- мостей в явную функциональную зависимость.Для проведения этой опера- ции необходимо ко множеству имен атрибутов правой части идентичной функциональной зависимости прибавить те атрибуты из ее левой части, которые в правой части еще не содержатся. Функциональные зависимости,полученные в результате выполнения аксиомы ФЗ1 назовем ПРИНЦИПИАЛЬНО НЕ СВОДИМЫМИ К ПРАВИЛЬНЫМ.Принципи- ально не сводимые к правильным - это такие функциональные зависимос- ти,у которых в результате выполнения операции полной или неполной в правой части образуется пустое множество имен атрибутов. Из соображения минимальной избыточности функциональные зависи- мости в замыкании следует представлять в правильной форме. Замыкание,в котором отсутствуют неправильные функциональные за- висимости,назовем УСЛОВНО-ПРАВИЛЬНЫМ. Условно-правильное замыкание,в котором отсутствуют функциональ- ные зависимости,принципиально не сводимые к правильным,назовем ПРИН- ЦИПИАЛЬНО ПРАВИЛЬНЫМ или просто ПРАВИЛЬНЫМ. Правильное замыкание,в котором отсутствуют ключевые зависимости и сверхключи,назовем ПРАВИЛЬНЫМ НЕКЛЮЧЕВЫМ ЗАМЫКАНИЕМ. Павомерность операций свертки и развертки легко может быть дока- зана при помощи соответствующих аксиом вывода функциональных зависи- мостей.Докажем это для операций полной свертки и полной развертки ( для операций неполной свертки и неполной развертки доказательство аналогично ). ДОКАЗАТЕЛЬСТВО : ________________ Задана правильная функциональная зависимость Ak...An -> Al...Am Докажем правомочность полной развертки. По аксиоме ФЗ1 Ak...An -> Ak...An По аксиоме ФЗ5 Ak...An -> Ak...An Al...Am Задана явная функциональная зависимость Ak...An -> Ak...An Al...Am Докажем правомочность полной свертки. По аксиоме ФЗ6 Ak...An -> Ak...An и Ak..An -> Al...Am СХОДНЫЕ ОПРЕДЕЛЕНИЯ ДЛЯ МНОГОЗНАЧНЫХ ЗАВИСИМОСТЕЙ. __________________________________________________ Для многозначных зависимостей,исходя из аксиом вывода и ПРЕДЛО- ЖЕНИЯ 2,можно дать аналогичные определения.То есть для многозначных зависимостей справедливы следующие определения и операции : 1) ЯВНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ. 2) НЕЯВНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ. 3) ЯВНЫЙ КЛЮЧ. 4) НЕЯВНЫЙ КЛЮЧ. 5) ЯВНЫЙ СВЕРХКЛЮЧ. 6) НЕЯВНЫЙ СВЕРХКЛЮЧ. 7) ПРАВИЛЬНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ. 8) НЕПРАВИЛЬНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ. 9) ПРАВИЛЬНЫЙ КЛЮЧ. 10)НЕПРАВИЛЬНЫЙ КЛЮЧ. 11)ПРАВИЛЬНЫЙ СВЕРХКЛЮЧ. 12)НЕПРАВИЛЬНЫЙ СВЕРХКЛЮЧ. 13)ИДЕНТИЧНЫЙ КЛЮЧ. 14)ИДЕНТИЧНЫЙ СВЕРХКЛЮЧ. 15)ИДЕНТИЧНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ. 16)МНОЖЕСТВО ИДЕНТИЧНЫХ МНОГОЗНАЧНЫХ ЗАВИСИМОСТЕЙ. 17)ПОЛНОЕ МНОЖЕСТВО ИДЕНТИЧНЫХ МНОГОЗНАЧНЫХ ЗАВИСИМОСТЕЙ. 18)МНОЖЕСТВО ИДЕНТИЧНЫХ КЛЮЧЕЙ. 19)ПОЛНОЕ МНОЖЕСТВО ИДЕНТИЧНЫХ КЛЮЧЕЙ. 20)МНОЖЕСТВО ИДЕНТИЧНЫХ СВЕРХКЛЮЧЕЙ. 21)ПОЛНОЕ МНОЖЕСТВО ИДЕНТИЧНЫХ СВЕРХКЛЮЧЕЙ. 22)ОПЕРАЦИЯ ПОЛНОЙ СВЕРТКИ. 23)ОПЕРАЦИЯ ПОЛНОЙ РАЗВЕРТКИ. 24)ОПЕРАЦИЯ НЕПОЛНОЙ или ЧАСТИЧНОЙ СВЕРТКИ. 25)ОПЕРАЦИЯ НЕПОЛНОЙ или ЧАСТИЧНОЙ РАЗВЕРТКИ. 26)МНОГОЗНАЧНЫЕ ЗАВИСИМОСТИ,ПРИНЦИПИАЛЬНО НЕ СВОДИМЫЕ К ПРАВИЛЬ- НЫМ. 27)МНОЖЕСТВО МНОГОЗНАЧНЫХ ЗАВИСИМОСТЕЙ,ПРИНЦИПИАЛЬНО НЕ СВОДИМЫХ К ПРАВИЛЬНЫМ. 28)УСЛОВНО ПРАВИЛЬНОЕ ЗАМЫКАНИЕ. 29)ПРИНЦИПИАЛЬНО ПРАВИЛЬНОЕ ( или просто ПРАВИЛЬНОЕ ) ЗАМЫКАНИЕ. 30)ПРАВИЛЬНОЕ НЕКЛЮЧЕВОЕ ЗАМЫКАНИЕ. Вновь вернемся к классификации функциональных зависимостей,толь- ко теперь уже будем работать с правильным неключевым замыканием.Поми- мо вышеприведенных типов функциональных зависимостей в правильном не- ключевом замыкании могут присутствовать зависимости,принадлежащие к другим типам.Поэтому введем следующие определения. ИЗБЫТОЧНОЙ ФУНКЦИОНАЛЬНОЙ ЗАВИСИМОСТЬЮ ПЕРВОГО ТИПА является функциональная зависимость вида Z -> Y,принадлежащая правильно- му неключевому замыканию,в котором помимо данной функциональной зави- симости присутствует еще хотя бы одна зависимость вида X -> Y,причем X=Z.То есть избыточная функциональная зависимость первого типа - это такая зависимость,которая входит в замыкание более одного раза.Подоб- ное может произойти в результате следующих событий : 1)Одну и ту же зависимость ввели дважды или более раз из-за нев- нимательности при работе с компьютером. 2)Одну и ту же функциональную зависимость ввели дважды или более раз в множество заданных функциональных зависимостей СЛУЧАЙНО при анализе семантики данных. 3)Одна и та же функциональная зависимость появилась в правильном неключевом замыкании два или более раз в результате операций полной и неполной сверток. 4)Одна и та же функциональная зависимость появилась в правильном неключевом замыкании два или более раз в результате применения аксиомы транзитивности. 5)Одна и та же функциональная зависимость появилась в правильном неключевом замыкании два или более раз в результате применения аксиомы объединения. 6)Одна и та же функциональная зависимость появилась в правильном неключевом замыкании два или более раз в результате приведения избыточной функциональной зависимости третьего типа к неизбы- точной форме. НЕИЗБЫТОЧНЫМ ПРАВИЛЬНЫМ НЕКЛЮЧЕВЫМ ЗАМЫКАНИЕМ ПЕРВОГО ТИПА назо- вем такое правильное неключевое замыкание,в котором отсутствуют избы- точные функциональные зависимости первого типа.То есть каждая функци- ональная зависимость должна входить в правильное неключевое замыкание НЕ БОЛЕЕ ОДНОГО РАЗА. ИЗБЫТОЧНОЙ ФУНКЦИОНАЛЬНОЙ ЗАВИСИМОСТЬЮ ВТОРОГО ТИПА является функциональная зависимость вида Z -> Y,принадлежащая правильно- му неключевому замыканию,в котором помимо данной функциональной зави- симости присутствует еще хотя бы одна зависимость вида X -> Y,причем X является подмножеством Z. ПРИМЕР. Задано отношение R(X1,X2,X3,X4,X5,X6,X7) и множество функцио- нальных зависимостей F. F={ X1 X2 -> X3 X4 X5,X1 -> X3 X4 X5,...,X5 X6 -> X7 } В данном множестве функциональных зависимостей зависимость X1 X2 -> X3 X4 X5 является избыточной зависимостью второго типа,поскольку существует зависимость X1 -> X3 X4 X5,левая часть которой - подмножество левой части функциональной зависимости X1 X2 -> X3 X4 X5.Такие зависимости могут появиться в результате событий,описанных в пунктах 3)...6) для избыточных функциональных зависимостей первого типа.Также они могут быть введены изначально в множество заданных зависимостей. НЕИЗБЫТОЧНЫМ ПРАВИЛЬНЫМ НЕКЛЮЧЕВЫМ ЗАМЫКАНИЕМ ВТОРОГО ТИПА назо- вем такое правильное неключевое замыкание,в котором отсутствуют избы- точные функциональные зависимости второго типа. ИЗБЫТОЧНОЙ ФУНКЦИОНАЛЬНОЙ ЗАВИСИМОСТЬЮ ТРЕТЬЕГО ТИПА является функциональная зависимость вида WZ -> XY,принадлежащая правильно- му неключевому замыканию,причем здесь возможны следующие случаи : 1)Множество W не пересекается с множеством Z,множество X пересе- кается с множеством Y.Данная ситуация может возникнуть,напри- мер,в результате применения аксиом объединения,рефлексивности и продолжения,которое мы назовем одним из вариантов операции СЛОЖЕНИЯ и которое определим в дальнейшем. ПРИМЕР : Даны две функциональные зависимости : X2 -> X3 X4 X5,X1 -> X4 X5 X6 ; Применим операцию сложения Получим : X1 X2 -> X3 X4 X5 X4 X5 X6. Подобные зависимости назовем ПРАВОСТОРОННИМИ ИЗБЫТОЧНЫМИ ФУНКЦИ- ОНАЛЬНЫМИ ЗАВИСИМОСТЯМИ ТРЕТЬЕГО ТИПА. 2)Множество W пересекается с множеством Z,множество X не пересе- кается с множеством Y.Данная ситуация может возникнуть,напри- мер,в результате применения одного из вариантов операции сло- жения,которую мы определим в дальнейшем. ПРИМЕР : Даны две функциональные зависимости : X1 X2 -> X3 X5,X1 X2 -> X4 X6 ; Применим операцию сложения Получим : X1 X2 X1 X2 -> X3 X4 X5 X6. Подобные зависимости назовем ЛЕВОСТОРОННИМИ ИЗБЫТОЧНЫМИ ФУНКЦИ- ОНАЛЬНЫМИ ЗАВИСИМОСТЯМИ ТРЕТЬЕГО ТИПА. 3)Множество W пересекается с множеством Z,множество X пересека- ется с множеством Y.Данная ситуация может возникнуть,например, в результате применения одного из вариантов операции сложения, которую мы определим в дальнейшем. ПРИМЕР : Даны две функциональные зависимости : X1 X2 -> X3 X5,X1 X2 -> X5 X6 ; Применим операцию сложения Получим : X1 X2 X1 X2 -> X3 X5 X5 X6. Подобные зависимости назовем СМЕШАННЫМИ ИЗБЫТОЧНЫМИ ФУНКЦИ- ОНАЛЬНЫМИ ЗАВИСИМОСТЯМИ ТРЕТЬЕГО ТИПА. Избыточные функциональные зависимости третьего типа могут появ- ляться также в результате событий,описанных в пунктах 1)-2) для избы- точных функциональных зависимостей первого типа. НЕИЗБЫТОЧНЫМ ПРАВИЛЬНЫМ НЕКЛЮЧЕВЫМ ЗАМЫКАНИЕМ ТРЕТЬЕГО ТИПА назо- вем такое правильное неключевое замыкание,в котором отсутствуют пра- восторонние избыточные функциональные зависимости третьего типа,лево- сторонние избыточные функциональные зависимости третьего типа и сме- шанные избыточные функциональные зависимости. ИЗБЫТОЧНЫЕ ФУНКЦИОНАЛЬНЫЕ ЗАВИСИМОСТИ ЧЕТВЕРТОГО ТИПА - это та- кие упорядоченные зависимости любого типа и/или неупорядоченные зави- симости,в которых записаны одни и те же имена атрибутов,но только в различных порядках,например, X1 X2 X3 -> X5 X6 X4 и X3 X2 X1 -> X4 X6 X5 - это избыточные функциональные зависимости четвертого типа.Определение упорядоченных и неупорядоченных зависимостей будет дано ниже.Данные зависимости могут появляться в результате тех же событий,что и избы- точные функциональные зависимости первого типа. НЕИЗБЫТОЧНЫМ ПРАВИЛЬНЫМ НЕКЛЮЧЕВЫМ ЗАМЫКАНИЕМ ЧЕТВЕРТОГО ТИПА назовем такое правильное неключевое замыкание,в котором отсутствуют избыточные функциональные зависимости четвертого типа. НЕИЗБЫТОЧНЫМ ПРАВИЛЬНЫМ НЕКЛЮЧЕВЫМ ЗАМЫКАНИЕМ назовем такое пра- вильное неключевое замыкание,в котором отсутствуют избыточные функци- ональные зависимости ВСЕХ типов.В дальнейшем неизбыточное правильное неключевое замыкание будем называть ЗАМЫКАНИЕМ ТИПА А. УПОРЯДОЧЕННАЯ ФУНКЦИОНАЛЬНАЯ ЗАВИСИМОСТЬ - это такая зависи- мость,в записи которой все имена атрибутов следуют строго в порядке возрастания или убывания порядковых номеров,например : X1 X2 X3 -> X4 X5 X10,X1 X3 -> X2 X4 - упорядоченные функциональные зависимости. ФУНКЦИОНАЛЬНАЯ ЗАВИСИМОСТЬ С УПОРЯДОЧЕННОЙ ПРАВОЙ ЧАСТЬЮ - это такая зависимость,в записи правой части которой все имена атрибутов следуют строго в порядке возрастания или убывания порядковых номеров, например,X1 X3 X2 -> X4 X5 X10 - функциональная зависимость с упоря- доченной правой частью. ФУНКЦИОНАЛЬНАЯ ЗАВИСИМОСТЬ С УПОРЯДОЧЕННОЙ ЛЕВОЙ ЧАСТЬЮ - это такая зависимость,в записи левой части которой все имена атрибутов следуют строго в порядке возрастания или убывания порядковых номеров, например,X1 X2 X3 -> X5 X4 X10 - функциональная зависимость с упоря- доченной правой частью. НЕУПОРЯДОЧЕННАЯ ФУНКЦИОНАЛЬНАЯ ЗАВИСИМОСТЬ - это такая зависи- симость,в записи которой имена атрибутов следуют в произвольном по- рядке,например,X1 X3 X2 -> X5 X4 X10 - неупорядоченная функциональная зависимость. Замыкание типа А,в котором содержатся только упорядоченные функ- циональные зависимости,назовем ЗАМЫКАНИЕМ ТИПА АB1. Замыкание типа А,в котором содержатся только функциональные за- висимости с упорядоченной правой частью,назовем ЗАМЫКАНИЕМ ТИПА АB2. Замыкание типа А,в котором содержатся только функциональные за- висимости с упорядоченной левой частью,назовем ЗАМЫКАНИЕМ ТИПА АB3. Замыкание типа А,в котором содержатся только неупорядоченные функциональные зависимости,назовем ЗАМЫКАНИЕМ ТИПА АB4. Замыкание типа А,в котором содержатся упорядоченные функциональ- ные зависимости любых типов,а также неупорядоченные зависимости,назо- вем ЗАМЫКАНИЕМ ТИПА B.В дальнейшем будем работать с замыканием типа B,поскольку желательно сделать так,чтобы создаваемый алгоритм,приво- дящий заданное отношение к той или иной нормальной форме,не делал различий между упорядоченными и неупорядоченными функциональными за- висимостями,так как они отображают одну и ту же информацию.При работе с замыканием типа B,у нас не вознивает необходимость в применении ал- горитмов сортировки,если упорядоченные и неупорядоченные функциональ- ные зависимости обрабатываются ОДИНАКОВО,без всяких различий между ними. Все,сказанное выше,справедливо и для многозначных зависимостей. Дадим теперь список определенных понятий,которые определены и для многозначных зависимостей. 1) ИЗБЫТОЧНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ ПЕРВОГО ТИПА. 2) НЕИЗБЫТОЧНОЕ ПРАВИЛЬНОЕ НЕКЛЮЧЕВОЕ ЗАМЫКАНИЕ ПЕРВОГО ТИПА. 3) ИЗБЫТОЧНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ ВТОРОГО ТИПА. 4) НЕИЗБЫТОЧНОЕ ПРАВИЛЬНОЕ НЕКЛЮЧЕВОЕ ЗАМЫКАНИЕ ВТОРОГО ТИПА. 5) ИЗБЫТОЧНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ ТРЕТЬЕГО ТИПА. A)ПРАВОСТОРОННЯЯ ИЗБЫТОЧНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ ТРЕТЬЕГО ТИПА. B)ЛЕВОСТОРОННЯЯ ИЗБЫТОЧНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ ТРЕТЬЕГО ТИПА. C)СМЕШАННАЯ ИЗБЫТОЧНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ ТРЕТЬЕГО ТИПА. 6) НЕИЗБЫТОЧНОЕ ПРАВИЛЬНОЕ НЕКЛЮЧЕВОЕ ЗАМЫКАНИЕ ТРЕТЬЕГО ТИПА. 7) ИЗБЫТОЧНАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ ЧЕТВЕРТОГО ТИПА. 8) НЕИЗБЫТОЧНОЕ ПРАВИЛЬНОЕ НЕКЛЮЧЕВОЕ ЗАМЫКАНИЕ ЧЕТВЕРТОГО ТИПА. 9) НЕИЗБЫТОЧНОЕ ПРАВИЛЬНОЕ НЕКЛЮЧЕВОЕ ЗАМЫКАНИЕ - ЗАМЫКАНИЕ ТИ- ПА А. 10)УПОРЯДОЧЕННАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ. 11)МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ С УПОРЯДОЧЕННОЙ ПРАВОЙ ЧАСТЬЮ. 12)МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ С УПОРЯДОЧЕННОЙ ЛЕВОЙ ЧАСТЬЮ. 13)НЕУПОРЯДОЧЕННАЯ МНОГОЗНАЧНАЯ ЗАВИСИМОСТЬ. 14)ЗАМЫКАНИЕ ТИПА АB1. 15)ЗАМЫКАНИЕ ТИПА АB2. 16)ЗАМЫКАНИЕ ТИПА АB3. 17)ЗАМЫКАНИЕ ТИПА АB4. 18)ЗАМЫКАНИЕ ТИПА B. Вновь вернемся к функциональным зависимостям.Помимо их вышепри- веденных типов можно выделить еще несколько. НЕИНЕРТНОЙ ИЛИ АКТИВНОЙ ФУНКЦИОНАЛЬНОЙ ЗАВИСИМОСТЬЮ назовем та- кую зависимость из нескольких других с эквивалентными левыми частями, у которой в правой части содержится список всех тех имен атрибутов, которые содержатся в правых частях всех остальных функциональных за- висимостей с эквивалентной левой частью,то есть активная зависимость получается в результате совокупного объединения всех функциональных зависимостей с эквивалентными левыми частями. ПРИМЕР : Задана совокупность функциональных зависимостей FF = {X1 X2 -> X3 X4,X1 X2 -> X3,X1 X2 -> X4 X5 X6,X1 X2 -> X7 X8 X4} Требуется построить правильную неизбыточную активную зависимость.При- меним аксиому объединения.Результат : X1 X2 -> X3 X4 X5 X6 X7 X8 - правильная неизбыточная активная зависимость. МНОЖЕСТВОМ ИНЕРТНЫХ ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ называется такое множество зависимостей,которое может быть получено из активной зави- симости в результате всех возможных декомпозиций. ПРИМЕР : Дана активная зависимость X1 X2 -> X3 X4 X5.Построить множество инертных зависимостей.Решение : применим аксиому декомпозиции.Получим искомое множество - { X1 X2 -> X3, X1 X2 -> X4, X1 X2 -> X5, X1 X2 -> X3 X4,X1 X2 -> X3 X5,X1 X2 -> X4 X5 }. Совокупность множества инертных функциональных зависимостей и активной зависимости назовем МНОЖЕСТВОМ ПРЕДСТАВИМЫХ ЗАВИСИМОСТЕЙ. Это множество,также как и полное множество идентичных зависимостей, может быть представлено всего одной функциональной зависимостью,- в данном случае активной,из которой можно при необходимости вывести все инертные зависимости. Замыкание типа B,в котором присутствуют только активные зависи- симости назовем ЗАМЫКАНИЕМ ТИПА C. ПРИМЕЧАНИЕ : функциональную зависимость,в правой части которой содержится всего один атрибут,и больше нет ни одной такой зависимос- ти,с которой рассматриваемую можно было бы объединить,применив аксио- му объединения,назовем ЭЛЕМЕНТАРНОЙ АКТИВНОЙ ЗАВИСИМОСТЬЮ.Естествен- но,что в замыкание типа C такие зависимости могут входить. Таким образом,можно уточнить определение БКНФ следующим образом : нормализованное отношение R находится в БКНФ,если каждая активная де- терминанта является возможным ключом.В самом деле,пусть задано отно- шение R(X1,X2,X3,X4,X5,X6) и его замыкание F+,состоящее всего из од- ной функциональной зависимости X1 X2 -> X3 X4 X5 X6.По определению это отношение находится в БКНФ,так как данная зависимость является возможным ключом.Добавим к заданному замыканию еще одну зависимость - X1 X2 -> X3 X4.Эта зависимость не является возможным ключом,она - его подмножество,и она может быть выведена из этого ключа при помощи ак- сиомы декомпозиции.Согласно определению Цикритзиса,отношение уже не находится в БКНФ,поскольку последняя детерминанта не является возмож- ным ключом.Поэтому мы должны были бы провести декомпозицию отношения, однако,помимо зависимости X1 X2 -> X3 X4 в замыкание можно добавить еще целое множество подобных ей зависимостей,каждая из которых может быть выведена из возможного ключа при помощи аксиомы декомпозиции.Ко- роче говоря,стандартное определение БКНФ звучит так : нормализованное отношение находится в БКНФ,если каждая элементарная активная детерми- нанта является возможным ключом.В итоге исходное отношение у нас не- минуемо должно распасться на столько результирующих отношений,сколько у нас элементарных активных функциональных зависимостей,то есть на четыре отношения.Однако на практике этого не происходит.Налицо проти- воречие,которое удалось устранить. К сожалению,приведенные выше определения не действительны в от- ношении многозначных зависимостей,поскольку для тех действует совсем другая аксиома декомпозиции. Кроме того,алгоритм Цикритзиса для построения замыкания является неполным,поскольку он теряет часть функциональных зависимостей.Данный алгоритм использует аксиомы рефлексивности,транзитивности и дополне- ния,однако возможны ситуации,когда не учитывается часть транзитивных зависимостей,например : задано отношение R(X1,X2,X3,X4,X5,X6) и фун- кциональные зависимости X1 -> X2 X3 X4,X3 X4 -> X5 X6.Требуется при- вести это отношение к БКНФ.Если мы воспользуемся алгоритмом Цикритзи- са без учета аксиомы декомпозиции,то у нас получится единственный возможный ключ X1 X3 X4 -> X2 X5 X6,тогда разложение в БКНФ будет следующим : R1(X3,X4,X5,X6) и R2(X1,X3,X4,X2) X3 X4 -> X5,X6 X1 X3 X4 -> X2 Если же мы добавим аксиому декомпозиции,то у нас появятся следу- ющие функциональные зависимости : X1 -> X3 X4,а так как X3 X4 -> X5 X6,то X1 -> X2 X3 X4 X5 X6 - единственный возможный ключ.Тогда разложение в БКНФ будет следующим : R1(X3,X4,X5,X6) и R2(X1,X2,X3,X4) X3 X4 -> X5 X6 X1 -> X2 X3 X4 Как видно из примера,возможный ключ получился на два атрибута короче, что позволит сэкономить место на диске при созданнии индексного фай- ла. Введем теперь операцию СЛОЖЕНИЯ.Операцией сложения называется такая операция,в результате действия которой из двух и более зависи- мостей получается еще одна,причем в ее левую часть входят не более одного раза все атрибуты,содержащиеся во всех левых частях исходных функциональных зависимостей,а в правую часть входят не более одного раза все атрибуты,содержащиеся во всех правых частях исходных функци- ональных зависимостей.Правомерность этой операции следует из аксиом вывода для функциональных и многозначных зависимостей.Можно показать, что аксиома объединения - частный случай операции сложения.Для созда- ваемого алгоритма операция сложения не так уж и важна,поскольку с ее помощью строятся,в основном,неполные функциональные зависимости,но в дальнейшем аксиому объединения будем называть операцией сложения. Перейдем теперь к рассмотрению избыточности.Введем понятие СЛОЖ- НОСТИ ОТНОШЕНИЯ.В первом приближении сложностью отношения назовем ко- личество атрибутов исходного ненормализованного отношения.Тогда НОР- МАЛИЗОВАННОЙ СЛОЖНОСТЬЮ назовем количество атрибутов того же отноше- ния,но только уже нормализованного.И,наконец,ИЗБЫТОЧНОСТЬЮ ОТНОШЕНИЯ назовем разность между нормализованной сложностью и сложностью отно- шения. ОТНОСИТЕЛЬНОЙ НОРМАЛИЗОВАННОЙ СЛОЖНОСТЬЮ назовем количество от- ношений,которые были получены из исходного при его нормализации в ре- зультате декомпозиций.ОТНОСИТЕЛЬНУЮ СЛОЖНОСТЬ примем равной единице, поскольку исходное отношение у нас одно.Тогда ОТНОСИТЕЛЬНОЙ ИЗБЫТОЧ- НОСТЬЮ назовем разность между относительной нормализованной сложнос- тью и сложностью отношения.АБСОЛЮТНОЙ ИЗБЫТОЧНОСТЬЮ ОТНОШЕНИЯ назовем назовем сумму избыточности и относительной избыточности,при этом надо помнить,что при нормализации отношения избыточность отношения будем считать важнее относительной избыточности;поэтому относительную избы- точность будем уменьшать только в том случае,если при ее уменьшениии уменьшается избыточность отношения ( или по крайней мере избыточность отношения остается на том же уровне ).Абсолютная избыточность отноше- ния связана с понятием мощности множества.Чтобы избыточность нормали- зованного отношения была меньше,необходимо проводить декомпозиции от- ношений,используя такие функциональные зависимости из созданного за- мыкания,левые части которых на момент декомпозиции минимальны,а пра- вые - максимальны.Если после разложения подобным образом избыточность и абсолютную избыточность отношения уменьшить нельзя,то замыкание,по зависимостям которого проводилось разложение,назовем ИДЕАЛЬНЫМ. ПРИМЕР : Задано отношение R(X1,X2,X3,X4,X5,X6,X7,X8,X9,X10) и идеальное замыкание типа C - { X1 -> X2,X3 -> X4,X5 -> X6,X7 -> X8,X9 -> X10 }. Разложим отношение в БКНФ : R1(X1,X2) R2(X3,X4) R3(X5,X6) R4(X7,X8) R5(X9,X10) X1 -> X2 X3 -> X4 X5 -> X6 X7 -> X8 X9 -> X10 R6(X1,X3,X5,X7,X9) X1 X3 X5 X7 X9 -> X1 X3 X5 X7 X9 Здесь следует ввести понятие КЛЮЧЕВОЙ ИЗБЫТОЧНОСТИ,которая важна при создании индексных файлов,и которую также желательно уменьшить.Ключе- вой избыточностью назовем количество первичных атрибутов в результи- рующих отношениях. В данном случае : избыточность отношения равна 5 относительная избыточность равна 5 абсолютная избыточность равна 10 ключевая избыточность равна 10 В данном примере полученное разложение является оптимальным;вве- дем теперь в идеальное замыкание еще две функциональные зависимости : X3 X5 -> X8 X10 X1,X7 X9 -> X4 X6 X2 и разложим исходное отношение в БКНФ.Проведем разложение точно также,как в случае с идеальным замыка- нием.Теперь будем считать избыточности полученного разложения опорны- ми точками,увеличивать значения которых мы не имеем права.Дальше вос- пользуемся методом ОГРАНИЧЕННОГО ПЕРЕБОРА,суть которого будет изложе- на ниже,и посмотрим,нельзя ли еще уменьшить избыточность.В итоге по- лучим следующее оптимальное разложение : R1(X3,X5,X8,X10,X1) R2(X7,X9,X4,X6,X2) R3(X3,X5,X7,X9) X3 X5 -> X8 X10 X1 X7 X9 -> X4 X6 X2 X3 X5 X7 X9 -> X3 X5 X7 X9 В данном случае : избыточность отношения равна 4 относительная избыточность равна 2 абсолютная избыточность равна 6 ключевая избыточность равна 8 Рассмотрим теперь метод ограниченного перебора.Его использование может быть полезно тогда,когда при разложении отношения часть функци- ональных зависимостей теряется,как это было показано выше. Начиная разложение в БКНФ,мы должны найти в замыкании типа C не- раскладываемую зависимость ( то есть такую зависимость,которая станет ключом после декомпозиции исходного отношения;это нужно для того,что- бы одно из полученных отношений автоматически оказалось в БКНФ ),у которой левая часть минимальна,а правая - максимальна,и выполнить первую декомпозицию.Затем мы модифицируем наше замыкание,запомнив в специальном файле разрушенные зависимости ( если таковые окажутся ) и проверим то отношение,с которым мы будем работать дальше,не находится ли и оно в БКНФ.Здесь же необходимо провести поиск,чтобы выяснить,нет ли в исходном замыкании зависимостей,которые окажутся ключами для двух полученных отношений.Из замыкания для того отношения,с которым мы будем работать дальше,такие зависимости требуется удалить.Затем мы будем повторять описанные действия до тех пор,пока все полученные от- ношения не окажутся в БКНФ.Если при этом не окажется разрушенных за- висимостей,то мы получили синтаксическое разложение в БКНФ,и задача решена.Если же разрушенные зависимости есть,то следует подсчитать из- быточность и попытаться,используя разрушенные зависимости,уменьшить избыточность,как это было показано выше. АЛГОРИТМ НОРМАЛИЗАЦИИ. _______________________ АРМ ЛОГИЧЕСКОГО ПРОЕКТИРОВАНИЯ БД : - ввод зависимостей ; - корректировка зависимостей ; - построение замыкания ; - выделение семантически оправданных зависимостей ; - нормализация отношения ; - просмотр результатов ; ВВОД ЗАВИСИМОСТЕЙ : - ввод функциональных зависимостей ; - ввод многозначных зависимостей ; ВВОД ФУНКЦИОНАЛЬНЫХ ЗАВИСИМОСТЕЙ : - ввод функциональных зависимостей в память ЭВМ ; - представление функциональных зависимостей в пра- вильной форме,а также приведение избыточных зависи- мостей третьего типа к неизбыточной форме ; - выделение ключей и сверхключей ; - запись функциональных зависимостей на диск ; ВВОД МНОГОЗНАЧНЫХ ЗАВИСИМОСТЕЙ : - ввод многозначных зависимостей в память ЭВМ ; - представление многозначных зависимостей в пра- вильной форме,а также приведение избыточных зависи- мостей третьего типа к неизбыточной форме ; - выделение ключей и сверхключей ; - запись многозначных зависимостей на диск ; КОРРЕКТИРОВКА ЗАВИСИМОСТЕЙ : - просмотр функциональных зависимостей ; - просмотр многозначных зависимостей ; - удаление функциональных зависимостей ; - удаление многозначных зависимостей ; - добавление функциональных зависимостей ; - добавление многозначных зависимостей ; - корректировка функциональных зависимостей ; - корректировка многозначных зависимостей ; ПОСТРОЕНИЕ ЗАМЫКАНИЯ : - построение замыкания типа C ( для функциональных зависимостей ; - построение замыкания типа B ( для многозначных за- висимостей ) ; - построение общего замыкания для функциональных и многозначных зависимостей ; ПОСТРОЕНИЕ ЗАМЫКАНИЯ ТИПА C : - проверка на нормальность формы отношения ; - устранение избыточных зависимостей всех типов ; - устранение инертных зависимостей ; - нахождение ВСЕХ транзитивных зависимостей ; - выделение ключей и сверхключей ; ПОСТРОЕНИЕ ЗАМЫКАНИЯ ТИПА B : - проверка на нормальность формы отношения ; - устранение избыточных зависимостей всех типов ; - выполнение операции сложения ( только аксиомы объ- единения ; - нахождение ВСЕХ транзитивных зависимостей ; - выделение ключей и сверхключей ; ПОСТРОЕНИЕ ОБЩЕГО ЗАМЫКАНИЯ ДЛЯ ФУНКЦИОНАЛЬНЫХ И МНОГОЗНАЧНЫХ ЗАВИСИМОСТЕЙ : - проверка на нормальность формы отношения ; - построение замыкания типа C ; - построение замыкания типа B ; - построение двухуровневого замыкания из замыкания типа C и замыкания типа B для совокупности функцио- ональных и многозначных зависимостей ; - выделение ключей и сверхключей ; ВЫДЕЛЕНИЕ СЕМАНТИЧЕСКИ ОПРАВДАННЫХ ЗАВИСИМОСТЕЙ : - выделение семантически оправданных зависимостей из замыкания типа C ; - выделение семантически оправданных зависимостей из замыкания типа B ; - выделение семантически оправданных зависимостей из двухуровневого замыкания для совокупности функ- циональных и многозначных зависимостей ; НОРМАЛИЗАЦИЯ ОТНОШЕНИЯ : - проверка на нормальность формы отношения ; - нормализация для идеального замыкания ; - уменьшение избыточности при помощи метода ограни- ченного перебора ; _________________________________________________________________________ А вот технической задание на создание АРМА ''НОРМАЛИЗАТОР''. То же требо- вание скорости работы сохраняет свою актуальность и для Партнерской Сис- темы ЗОРАН! _________________________________________________________________________ ТЕХНИЧЕСКОЕ ЗАДАНИЕ. _____________________ 1).ТЕМА : Логическое проектирование БД. 2).ЦЕЛЬ : Разложение заданного отношения в 4НФ. 3).ТРЕБОВАНИЯ К ПРОГРАММНОМУ ПРОДУКТУ. a).ФУНКЦИОНАЛЬНЫЕ ТРЕБОВАНИЯ. _____________________________ a.1). На первое место ставится скорость работы,поскольку приведение заданного отношения к 4НФ будет происходить в режиме диалога с пользователем.Для обеспечения высокой скорости работы нужно : A). Проанализировать все существующие алгоритмы разложения и, если это только возможно,создать новый ( может быть даже принципиально новый ) алгоритм,превосходящий все остальные быстротой выполнения.Причем здесь по возможности следует отказаться от реализации NP-полных задач,таких,например,как нахождение возможных ключей. Б). Совместить некоторые действия,выполняемые программой,друг с другом.Например,можно совместить ввод зависимостей ( как функциональных,так и многозначных ) с экрана и часть ( же- лательно как можно большую ) алгоритма нормализации. ПРИМЕЧАНИЕ : При написании программы был использован весьма оригинальный и очень быстродействующий алгоритм сортировки и устранения одинаковых имен атрибутов как из левых,так и из правых частей зависимостей.Все описанные действия выпол- няются всего за два прохода сортируемого массива. В). Ввод и обработку зависимостей следует написать на языке низкого ( ассемблер ) или среднего ( си ) уровня. a.2). Достаточно важным условием для повышения быстродействия работы программы является тот объем памяти,который будут занимать фун- кциональные ( многозначные ) зависимости на диске.Для минимиза- ции объема дискового пространства,занятого зависимостями,необ- ходимо : А). Разработать классификацию функциональных и многозначных за- висимостей,а также действия,позволяющие выводить из одних зависимостей другие ( на основе аксиом вывода зависимос- тей ).В дальнейшем будем,опираясь на классификацию,записы- вать на диск только такие зависимости,которые нужны для нормализации. Б). Основываясь на классификации зависимостей,ввести следующий принцип : В ЛЮБОЙ ЗАВИСИМОСТИ ИМЯ ЛЮБОГО АТРИБУТА ДОЛЖНО ВСТРЕЧАТЬСЯ НЕ БОЛЕЕ ОДНОГО РАЗА. В). Поскольку количество атрибутов в нормализуемом отношении пока не превосходит 253,каждый атрибут на диске должен за- нимать НЕ БОЛЕЕ ОДНОГО БАЙТА. ПРИМЕЧАНИЕ : для повышения быстродействия прогрсммы в каж- дую зависимость придется ввести два дополнительных поля по одному байту каждое.В эти поля будет записываться длина ле- вой и правой частей зависимости соотвоетственно. Г). Действия,которые нужно выполнить и над функциональными и над многозначными зависимостями,должны выполняться одними и теми же участками алгоритма. ПРИМЕЧАНИЕ : Чем меньше памяти на диске зависимости будут занимать зависимости,тем меньше времени будет занимать их обработка,а следовательно,повысится быстродействие програм- мы в целом. a.3). Выполнение пунктов a.1) и a.2) не должно приводить к увеличению избыточности ( по сравнению с уже существующими алгоритмами но- рмализации ).Уменьшение избыточности также можно поставить на одно из первых по важности мест при реализации алгоритма. ПРИМЕЧАНИЕ : понятие избыточности и все остальное,связанное с ним,подробно рассмотрено в пояснительной записке. a.4). Алгоритм должен учитывать три основные возможности,с которыми можно столкнуться при нормализации отношения : А). Задана совокупность функциональных зависимостей. Б). Задана совокупность многозначных зависимосте. В). Задана совокупность функциональных и многозначных зависи- мостей. a.5). Следует учесть принцип дальнейшего развития программы.ГЛОБАЛЬ- НАЯ цель при создании данного алгоритма была следующая : обес- печение автоматической перекачки информации из старых баз дан- ных в новые при изменении предметной области и входной структу- ры функциональных и многозначных зависимостей.Кроме того,соз- данный алгоритм после некоторых дополнений позволит проводить ( если только это позволят структуры функциональных и многоз- начных зависимостей ) синтаксическое разложение заданного отно- шения в 4НФ. ПРИМЕЧАНИЕ : именно из-за глобальной цели управляющая часть про- граммного комплекса ( ситема меню ) написана на языке СУБД типа CLIPPER. b).ТРЕБОВАНИЯ К НАДЕЖНОСТИ. ___________________________ b.1). Должна быть предусмотрена защита от аварийных ситуаций.Напри- мер,если необходимо открыть какой-либо файл,но сделать это не- возможно ( нет места на диске или что-нибудь подобное ),то про- грамма должна вывести сообщение об ошибке,и если из-за подобной ошибки дальнейшая работа невозможна,то программа должна завер- шить свою работу. b.2). Следует предусмотреть защиту от неправильных действий пользова- теля.В случае неправильного ввода зависимости с экрана либо ка- ких-нибудь подобных действий,программа должна выводить сообще- ние и не записывать неправильно введенную зависимость на диск. Подобное событие может произойти,например,когда пользователь ввел номер атрибута,превышающий по своему значению общее число атрибутов заданного отношения. b.3). Требования к удобству.При анализе семантики предметной области, а также при вводе функциональных и многозначных зависимостей совсем не нужно держать в голове их классификацию и думать, важна или не важна та или иная зависимость для процесса норма- лизации.Все необходимые действия и весь анализ зависимостей программа выполнит сама,а если ту или иную зависимость не нужно записывать на диск,то будет выведено соответствующее сообщение. СПИСОК ЛИТЕРАТУРЫ. (1) - КОПЕЙКИН М.В. ЛЕКЦИИ ПО БАЗАМ ДАННЫХ. (2) - ДРИБАС В.П.РЕЛЯЦИОННЫЕ МОДЕЛИ БАЗ ДАННЫХ.БГУ.МИНСК.БССР.1982 (3) - Е.А.НЕКЛЮДОВА,М.Ш.ЦАЛЕНКО.СИНТЕЗ ЛОГИЧЕСКОЙ СХЕМЫ РЕЛЯЦИОН- НЫХ БАЗ ДАННЫХ. ПРОГРАММИРОВАНИЕ,N 6,1979 (4) - К.ДЕЙТ.ВВЕДЕНИЕ В СИСТЕМЫ БАЗ ДАННЫХ. МОСКВА.НАУКА.1980. (5) - Д.ЦИКРИТЗИС.Ф.ЛОХОВСКИ.МОДЕЛИ ДАННЫХ.МОСКВА.ФИНАНСЫ И СТА- ТИСТИКА.1985 ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА. 1. ЖЕРНАК А.Н.МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО КУРСОВОМУ ПРОЕКТИРОВАНИЮ. СЗПИ.1992 2. ЖЕРНАК А.Н.АЛЕКСАНДРОВ Н.Н.РАБОТА С ДАННЫМИ НА ЭВМ.УЧЕБНОЕ ПО- СОБИЕ.СЗПИ.1985