Итак, информация по реляционным базам данных... Последняя редакторская правка - 1996 год. Из-за очень сильного противодействия моя работа по оформлению по- лученных результатов была прекращена... Мне пришлось делать тяжелый выбор: или, несмотря ни на что, продол- жать вести исследования, не имея впереди АБСОЛЮТНО никаких перспек- тив; или продолжить заниматься ИСКЛЮЧИТЕЛЬНО ПРАКТИЧЕСКОЙ РЕАЛИЗА- ЦИЕЙ УЖЕ ПОЛУЧЕННЫХ РЕЗУЛЬТАТОВ. Я выбрал последнее. А теория реляционных баз данных оказалась исключительно подходящим объектом-полигоном для проверки практической пригодности моей кон- цепции ИНФОРМАЦИОННЫХ ОБОБЩЕНИЙ. И это - ПЕРВЫЙ КИТ, на котором ба- зируется Партнерская Система ЗОРАН (ее практическая реализация). Ну, ВТОРОЙ КИТ - это и так понятно: концепция искусственного интел- лекта... В общем, используя информационные обобщения, мне удалось легко и просто доработать стандартную теорию реляционных баз данных, соз- дать на ее основе новую методику нормализации отношений, реализо- вать эту методику в виде конкретного алгоритма для макета АРМА ''НОРМАЛИЗАТОР''. Но об этом уже будет рассказано во второй части работы по реляционным базам данных. Первая же часть моей работы, опять-таки, компилятивная. Опять стоим ''на плечах гигантов''! ___________________________________________________________________ ИТАК, РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ ___________________________________________________________________ РЕЛЯЦИОННЫЕ БАЗЫ ДАННЫХ. ( РЕЦЕНЗИЯ НА КУРС ЛЕКЦИЙ ). Предлагаемая часть образовательной программы позволяет оз- накомить учащихся и студентов с основными теоретическими поло- жениями концепции БД,весьма важной в области компьютерной ин- дустрии,а также дать представление слушателям о месте и роли теории реляционных БД в общей системе методов написания прог- раммных продуктов различного назначения. В работе обобщены результаты исследований в области реля- ционных БД как российских ученых ( Неклюдовой,Цаленко,Дрибаса, Копейкина ),так и их зарубежных коллег ( Фэджина,Бернштейна, Ислура,Дейта,Цикритзиса,Лоховски,Мейера и других ) ; приводится сравнительная оценка существующих методов нормализации,описыва- ются их достоинства и недостатки.Также в курсе лекций определя- ются перспективы развития БД реляционного и нереляционного ти- пов. Рекомендуемая работа по БД реляционного типа обеспечивает высокий уровень подготовки учащихся и студентов в вышеупомяну- той области. Д.т.н.,зав.каф. СТ и ЭВМ СЗПИ Анкудинов Г.И. ___________________________________________________________________ ОГЛАВЛЕНИЕ. 1. Введение ................................................... 2. Информация и модели предметных областей .................... 3. Классификация систем управления базами данных .............. 4. Централизованное и децентрализованное программное обеспече- ние ........................................................ 5. Основные характеристики баз данных,отличающие их от файло- вых систем ................................................. 6. Основы реляционной модели баз данных ..................... 7. Отношение .................................................. 8. Алгебра отношений .......................................... 9. Специальные операции реляционной алгебры ................... 10. Операция деления ........................................... 11. Определение операции деления ............................... 12. Алгоритм операции деления ................................. 13. Заключение алгебры отношений ............................. 14. Предпосылки введения исчисления отношений ................ 15. Выполнение запроса типа 1 .................................. 16. Выполнение запроса типа 2 .................................. 17. Функциональные зависимости в отношениях .................... 18. Определение функциональной зависимости ................... 19. Полная функциональная зависимость .......................... 20. Детерминанта ............................................... 21. Возможный ключ ............................................. 22. Структура FD(w) ............................................ 23. Сверхключ .................................................. 24. Определения,вытекающие из понятия возможного ключа ......... 25. Аксиоматика функциональных зависимостей .................... 26. Возможные взаимосвязи функциональных зависимостей в отноше- ниях ....................................................... 27. Многозначные зависимости ................................... 28. Аксиоматика многозначных зависимостей ..................... 29. Концептуальный уровень реляционной модели ................ 30. Требования,предъявляемые к модели .......................... 31. Нормальные формы отношений ............................... 32. Зависимости соединения ................................... 33. Методы и способы решения задачи по нормализации отношений .. 34. Формальная постановка задачи проектирования реляционной схе- мы ......................................................... 35. Алгоритмы проектирования реляционной схемы базы данных ..... 36. Характеристики алгоритмов проектирования реляционных схем .. 37. Ограничения в способах реализации и недостатки ............ 38. Достоинства и недостатки реляционной модели .............. 39. Требования к разрабатываемому методу ...................... 40. Список литературы .......................................... 41. Дополнительная литература .................................. ___________________________________________________________________ В В Е Д Е Н И Е СОСТОЯНИЕ ВОПРОСА В НАСТОЯЩЕЕ ВРЕМЯ И ПЕРСПЕКТИВЫ ЕГО РАЗВИТИЯ. На первых этапах развития вычислительной техники решались, в основном,задачи вычислительного характера.Решения этих задач требовались для инженерных расчетов,которые отличались сложными алгоритмами и простыми данными.Однако,со временем область при- менения вычислительной техники расширялась. Так,например,в экономических задачах алгоритмы просты,а число данных велико,и их структура может быть очень сложной.Еще более сложная структура данных - в информационно-поисковых системах ; в этих системах элементы данных связаны между собой различными зависимостями. Наиболее важная и общая задача при работе с большими объ- емами данных - это поиск данных с определенными свойствами,при- чем время поиска в значительной мере определяется структурой данных. Основные идеи современной информационной технологии бази- руются на концепции баз данных : основа информационной техноло- гии - это данные,которые должны быть организованы в базу данных с целью адекватного отображения изменяющегося реального мира и удовлетворения информационных потребностей пользователей. В шестидесятые годы появились первые промышленные системы управления базами данных - СУБД - специализированные програм- мные средства,предназначенные для организации и ведения баз данных. В восьмидесятые годы появляется много систем,базирующихся на использовании знаний. Системы баз данных становятся с каждым годом все более ин- теллектуальными.На внешнем уровне их архитектуры реализуются разнообразные семантические модели данных,создаются " дружелюб- ные " интерфейсы для пользователей. В настоящее время разработаны следующие основные модели данных : сетевые,иерархические,реляционные,бинарные,семантичес- кие сети,фреймы. Среди всех моделей данных только одна стандартизована по множеству операций - это реляционная модель.Однако,современная теория реляционных баз данных противоречива.А из-за противоре- чий невозможно создать " лучший алгоритм " по представлению данных той или иной предметной области.Поэтому в будущем придется либо переработать теорию реляционных баз данных таким образом,чтобы она стала непротиворечивой,либо воспользо- ваться другими подходами - такими,например,как использование теории объектно-реляционных баз данных или применение понятия иерархических зависимостей,что позволит наиболее адекватно отображать предметную область в среде конкретной СУБД. ИHФOPMAЦИЯ И MOДEЛИ ПPEДMETHЫX OБЛACTEЙ.[ 1 ]. Bычиcлитeльнaя тexникa пpeднaзнaчeнa пpeждe вceгo для oбpaбoтки инфopмaции. Пoд инфopмaциeй здecь пoнимaютcя любыe cвeдeния o кaкoм- либo coбытии,cyщнocти,пpoцecce и т.п., являющиecя oбъeктoм нeкoтopыx oпepaций : вocпpиятия, пepeдaчи, пpeoбpaзoвaния, xpaнeния или иcпoльзoвaния. Для пoльзoвaтeлeй, иcпoльзyющиx инфopмaцию пocpeд- cтвoм вычиcлитeльнoй тexники,являeтcя кpaйнe вaжным, кaкими cpeдcтвaми инфopмaция oтoбpaжaeтcя в cрeдe вычиcлитeльнoй тexники, т.e. кaким oбpaзoм peaльный миp ( инфopмaция o peaльнoм миpe ) пocpeдcтвoм мoдeлeй пpeдcтaвлeн в пaмяти ЭBM. Koличecтвo мoдeлeй бeзгpaничнo, т.к. в пpинципe кaждый чeлoвeк мoдeлиpyeт peaльный миp ( пpeдмeтнyю oблacть ) c yчeтoм eгo интeллeктyaльныx вoзмoжнocтeй. Kaждый чeлoвeк, coздaвaя мoдeль пpeдмeтнoй oблacти, нa пepвoнaчaльнoм этaпe иcпoль- зyeт yнивepcaльнoe cpeдcтвo пpeдcтaвлeния инфopмaции - ecтecт- вeнный язык. Oднaкo,в cилy cпeцифики этoгo yнивepcaльнoгo cpeдcтвa и oтcyтcтвия пpeдeлa пoзнaния пpeдмeтнoй oблacти, тaкиe мoдeли нe пpиcпocoблeны для oтoбpaжeния в кoмпьютep- ныx cиcтeмax, xoтя и являютcя ocнoвoй ceмaнтики для пocлe- дyющeгo мoдeлиpoвaния и ocнoвoй мoдeлeй кoмпьютepнoгo пpeдcтaвлeния инфopмaции пpeдмeтнoй oблacти. Taким oбpaзoм, вoзникaeт пpoблeмa coздaния oбщeгo пoдxoдa к мoдeлиpoвaнию дaнныx, пpи этoм вaжнo, чтoбы тaкoй пoдxoд oбecпeчил нe тoль- кo идeнтификaцию пoнятий и cвoйcтв мoдeлeй дaнныx, нo и пocpeд- cтвoм caмoй мoдeли pacкpывaл cyщнocть дaнныx ( иx взaимocвязи ) и пpeдcтaвляeмoй ими инфopмaции. Moдeль дaнныx - этo cpeд- cтвo aбcтpaкции, кoтopoe интepпpeтиpyeт инфopмaциoннoe co- дepжaниe дaнныx пpeдмeтнoй oблacти, чacтичнo пpeдcтaвляя ce- мaнтикy дaнныx пpeдмeтнoй oблacти, то eсть сpeдcтвo,пepeдaющee чacтичныe знaния o peaльнoм миpe ( пpeдмeтнoй oблacти ). Инфopмaциoннoe coдepжaниe мoдeли дaнныx oтoбpaжaeтcя в кoмпьютepнoй cpeдe в видe бaзы дaнныx ( бaз дaнныx ).Ta- ким oбpaзoм,бaзa дaнныx являeтcя интeгpиpoвaнным xpaнилищeм дaнныx,кoтopoe пpeждe вceгo фopмиpyeтcя нa пpинципax, вклaды- вaeмыx в cмыcлoвoe coдepжaниe элeмeнтoв мoдeли дaнныx и тpeбoвaний пpилoжeний ( зaдaч ) пpeдмeтнoй oблacти. Oтмeтим, чтo фaйлoвaя cиcтeмa тaкжe иcпoльзyeт кaкиe-тo мoдeли пpeдмeтнoй oблacти, нo эти мoдeли в cвoeм бoль- шинcтвe,paзpaбaтывaютcя для кaждoгo пpилoжeния ( зaдaчи ) и нe yчитывaют интeгpaцию дaнныx. Ocнoвнoй цeлью coздaния cиcтeм yпpaвлeния бaзaми дaнныx являeтcя cнижeниe зaтpaт нa paзpaбoт- кy пpилoжeний ( зaдaч ), ycкopeниe пpoцecca пpoeктиpoвaния и чacтичнyю aвтoмaтизaцию пpoцecca пpoгpaммиpoвaния. CУБД - этo пpoгpaммнaя oбoлoчкa, pacшиpяющaя фyнкции OC,кoтopaя yпpaвляeт дocтyпoм к бaзaм дaнныx и oбecпeчи- вaeт cepвиcныe фyнкции для пoльзoвaтeля. Пoд бaнкoм дaнныx пoнимaют coвoкyпнocть бaз дaнныx c cooтвeтcтвyющeй им CУБД. KЛACCИФИKAЦИЯ CУБД.[ 1 ]. CУБД пoдpaздeляют : - пo типy пoддepживaeмыx мoдeлeй ( ceтeвыe, иepapxичecкиe, peляциoнныe, бинapныe, ceмaнтичecкиe ceти, фpeймы ); - пo типy взaимoдeйcтвия c oбpaбaтывaющeй пpoгpaммoй ; aвтoнoмныe и c включaющим языкoм пpoгpaммиpoвaния ; - пo типy apxитeктypы CУБД или пo ypoвням aбcтpaкции xpaнимoй инфopмaции. B нacтoящee вpeмя пpинятa чeтыpexypoвнeвaя apxитeктypa CУБД ; - инфoлoгичecкий ypoвeнь, кoнцeптyaльный ypoвeнь,внeшний ypoвeнь и внyтpeнний ypoвeнь.Ha кaждoм ypoв- нe пpиcyтcтвyeт мoдeль инфopмaции,кoтopaя cпeцифициpyeтcя c пoмoщью языкa oпиcaния дaннoгo ypoвня. Moдeль кaждoгo ypoв- ня,oпиcaннaя нa языкe oпиcaния, пpинятo нaзывaть cxeмoй.Пe- peвoд мoдeлeй ( oпиcaниe мoдeлeй ) из oднoгo ypoвня в дpyгoй ocyщecтвляeтcя c пoмoщью тpaнcляции. B зaвиcимocти oт видa пpeдcтaвлeния инфopмaции paзли- чaют cлeдyющиe типы cxeм : - инфoлoгичecкaя cxeмa, дaющaя oбщee инфopмaциoннo-лoгичecкoe пpeдcтaвлeниe oб инфopмaции пpeдмeтнoй oблacти ; - кoнцeптyaльнaя cxeмa, oпиcывaющaя инфopмaцию o пpeдмeтнoй oблacти в тepминax кoнкpeтнoй CУБД ; - внeшняя cxeмa, дaющaя пpeдcтaвлeниe инфopмaции o пpeдмeтнoй oблacти для пpиклaдныx пpoгpaмм и пoльзoвaтeлeй cиcтeмы ; - внyтpeнняя cxeмa, xapaктepизyющaя физичecкий ypoвeнь пpeдcтaвлeния инфopмaции. ЦEHTPAЛИЗOBAHHOE И ДEЦEHTPAЛИЗOBAHHOE ИHФOPMAЦИOHHOE OБECПEЧEHИE.[ 1 ]. Oтмeтим, чтo жизнecпocoбнocть пpoмышлeнныx CУБД oпpeдeля- eтcя пpeждe вceгo кoнцeптyaльным ypoвнeм, т.к. имeннo кoнцeп- тyaльный ypoвeнь cвязывaeт мeждy coбoй внyтpeнний и внeшний ypoвeнь и oбecпeчивaeт иx нeзaвиcимocть,то eсть измeнeниe мoдeли внyтpeннeгo ypoвня ( нaпpимep, в cлeдcтвиe нeoб- xoдимocти yвeличeния cкopocти oтвeтa нa кaкoй-либo зaпpoc к cиcтeмe ) нe пpивoдит к пepeдeлкe дpyгиx пpиклaдныx пpoг- paмм, иcпoльзyющиx этoт жe инфopмaциoнный фoнд. OCHOBHЫE XAPAKTEPИCTИKИ БAЗ ДAHHЫX, OTЛИЧAЮЩИE ИX OT ФAЙЛOBЫX CИCTEM.[ 1 ]. 1.- пoвышeниe нaдeжнocти, цeлocтнocти и coxpaннocти дaнныx ; 2.- coxpaнeниe зaтpaт интeллeктyaльнoгo тpyдa ; 3.- пpocтoтa и лeгкocть иcпoльзoвaния дaнныx, cлoжный дocтyп к дaнным ocyщecтвляeт CУБД ; 4.- нeзaвиcимocть пpиклaдныx пpoгpaмм oт измeнeний oпиcaний дaнныx и нaoбopoт ; 5.- пpocтoтa внeceний измeнeний и oбecпeчeниe дocтoвepнocти дaнныx ; 6.- oбecпeчeниe тpeбyeмoй cкopocти дocтyпa ; 7.- cтaндapтизaция дaнныx в пpeдeлax oднoй пpeдмeтнoй oблacти ; 8.- aвтoмaтизиpoвaннaя peopгaнизaция дaнныx ; 9.- зaщитa oт иcкaжeния и yничтoжeния ; 10.- coкpaщeниe дyблиpoвaния инфopмaции зa cчeт cтpyктypи- poвaния дaнныx ; 11.- мнoгoкpaтнoe иcпoльзoвaниe дaнныx ; 12.- oбpaбoткa нeзaплaниpoвaнныx зaпpocoв ; 13.- coздaниe пpeдпocылoк для pacпpeдeлeнныx бaз дaнныx. Основы реляционной модели баз данных ( БД ). При любом методе проектирования моделей предметной области основой является кодирование понятий и отношений между понятиями в модели данных.Реляционная модель данных берет в основу кодиро- вания понятие отношения.Эта модель наиболее абстрактная,она не различает понятия объекта и связи между объектами. [ 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 является подмножеством де- картова произведения. Имя отношения ( идентификатор ) и совокупность имен ат- рибутов составляют СХЕМУ ОТНОШЕНИЯ,например, ГРУППА(шифр группы, студент).Кортежи отношения могут со временем меняться,что будет соответствовать определенному событию в отображаемой ПРЕДМЕТНОЙ ОБЛАСТИ ( предметная область - это реальный мир,который посред- ством моделей отображается в памяти ЭВМ ).Именно это отличает понятие отношения реляционной модели от строгого математическо- го определения отношения,в котором говорится,что отношение оп- ределено и со временем не изменяется ; если же какой-нибудь кор- теж изменился,то это будет другое отношение. Совокупность схем отношений составляет СХЕМУ БД.Состояние схемы БД - это сама БД. Обычно схема базы данных (БД) состоит из небольшого числа схем отношений,но каждое отношение есть множество достаточно большой мощности. ПРИМЕР : Пусть имеется два множества F: { F1,F2,F3 } - множество факультетов G: { G1,G2,G3,G4,G5 } - множество групп На этих двух множествах можно задать отношение R,которое будем интерпретировать как " Распределение групп по факульте- там ".Тогда,отношение R есть множество пар,которое формально есть подмножество всех возможных пар. R нестрого включает F x G F = < F1,F2,F3 > нестрого включает < F1 G1 > G = < G1,G2,G3,G4,G5 > < F1 G2 > < F1 G3 > < F1 G4 > < F1 G5 > < F2 G1 > < F2 G2 > < F2 G2 > < F2 G4 > . . . . . . Отношение R,которое существует в реальности,является подм- ножеством декартова произведения и для некоторой предметной области оно может иметь вид F G --------¬ ¦ F1 G1¦ ¦ F2 G2¦ R = ¦ F2 G4¦ ¦ F3 G3¦ ¦ F3 G5¦ L-------- Так как эл-ты отношение представляют собой кортежи,одина- ковые по своей структуре,то отношение можно представить в форме таблицы R ( A1,A2 ),где А1 и А2 так называемые имена ат- рибутов,которые можно рассматривать как имена подмножеств,и на которых определено отношение R. АТРИБУТ есть подмножество соответсвующего домена,на ко- тором определено отношение.При этом,так как один и тот же домен может быть использован более одного раза при образовании отно- шения,то,следовательно,на нем может быть определено более од- ного атрибута,которым необходимо дать различные имена,т.к. со- ответствующие подмножества в общем случае выполняют различные роли и могут быть различимы. Имя отношения ( идентификатор ) и совокупность имен атри- бутов составляют схему отношения. Например, Группа ( Шифр группы,Студент ). [ 1 ]. АЛГЕБРА ОТНОШЕНИЙ. ПРИМЕЧАНИЕ : В основу данной главы положены лекции М.В.Ко- пейкина. [ 1 ]. В реляционном подходе ответ на конкретный запрос к БД также представляется в форме отношения,поэтому в основе средств,используемых для формирования запроса,может лежать ал- гебра отношений. Как известно,алгебра есть множество вида А : < H,S > ,где H - носитель ( в данном случае - множество отношений ) и S сигнатура ( в данном случае - множества операций над от- ношениями ). Существует много вариантов операций для реляционной ал- гебры,но мы изучим только операции,использованные Коддом (ос- новоположником реляционной модели ). Все множество S операций реляционной алгебры целесообраз- но разбить на два подмножества: Стандартные теоретико-множественные операции - объединение U R=R1 U R2 - пересечение ** - разность \ R=R1\R2 - декартово произведение х R=R1xR2 Специальные операции - проекцию Rрез(А)=R[A] - ограничение Rрез=R1[булевское выражение] - cоединение Rрез=R1[(булевское выражение)]R2 - деление Rрез=R1:R2 Операции реляционной алгебры унарны ( т.е. используют в ка- честве операнда только одно отношение ),либо бинарны,когда име- ются два операнда. Рассмотрим более подробно каждую операцию.Для двух отно- шений R1 и R2 представленных схемами: R1 (A1,A2, ... ,An) R2 (B1,B2, ... ,Bn) Операции объединения,пересечения и разности возможны толь- ко в том случае,когда отношения R1 и R2 являются ОБЪЕДИНИМЫ- МИ.Это означает,что степени объединяемых отношений одинаковы, а соответствующие атрибуты определены на одних и тех же доме- нах. В результате операции объединения получающееся отношение имеет ту же степень,что и исходное отношение Rрез (С1, ... ,Cn)=R1(A1,..,An) U R2(B1,...,Bn) ПРИМЕР : Пусть исходные отношения заданы табл.1 и табл.2 Табл.1 Изготовитель1(Главк,Изготовитель,Цех,Адрес,Имя детали) Г1 S2 D1 T2 A1 Г1 S3 D1 T2 A2 Г1 S1 D1 T1 A1 Г1 S4 D1 T2 A3 Г1 S1 D2 T1 B1 Табл.2 Изготовитель2(Главк,Изготовитель,Цех,Адрес,Имя детали) Г1 S1 D2 T1 B1 Г1 S1 D2 T4 B1 Тогда,результатом операции объединения Rз = Изготовитель1 U Изготовитель2 Rз (Главк,Изготовитель,Цех,Адрес,Имя детали) Г1 S2 D1 T2 A1 Г1 S3 D1 T2 A2 Г1 S1 D1 T1 A1 Г1 S4 D1 T2 A3 Г1 S1 D2 T1 B1 Г1 S1 D2 T4 B1 Результат операции пересечения также отношение,степень отноше- ния сохраняется,а мощность результирующего отношения лежит в пределах : 0 < Mрез <= min (M1,M2) Например : Изготовитель1 ** Изготовитель2 = R4 R4 (Главк,Изготовитель,Цех,Адрес,Имя детали) Г1 S1 D2 T1 B1 При операции взятия разности степень результирующего от- ношения тоже сохраняется,а мощность лежит в пределах : 0 <= Mрез <= M1 Например,операция разности Изготовитель1 \ Изготовитель2 (Главк,Изготовитель,Цех,Адрес,Имя детали) Г1 S2 D1 T2 A1 Г1 S3 D1 T2 A2 Г1 S1 D1 T1 A1 Г1 S4 D1 T2 A3 Для операции декартова произведения никаких ограничений на степени исходных отношений и природу атрибутов не наклады- вается.В результате этой операции осуществляется приписывание ( конкатенация ) всех строк второго операнда ко всем стро- кам первого операнда. СПЕЦИАЛЬНЫЕ ОПЕРАЦИИ РЕЛЯЦИОННОЙ АЛГЕБРЫ. ПРОЕКЦИЯ.Операция состоит в выделении одного или несколь- ких доменов в отдельную таблицу и вычеркивании повторяющихся строк. Например,проекция отношения R1 на домен с именем А обоз- начается Rрез(А) = R1[A] Операция ОГРАНИЧЕНИЯ или операция ВЫБОРА.Является унарной операцией,но в отличие от проекции ориентирована на выделение нужных строк отношения. Пусть исходное отношение задано схемой R1(A1 ... An) Символически операция записывается Rрез(А1...An) = R1[булевское выражение] R1(Шифр группы,Шифр cтуд,Специальность) Г1 Ш2 1 Г1 Ш3 1 Г1 Ш10 2 Г1 Ш15 3 Найти Студентов специальности 3 группы 2 Rрез(Шифр студ,Спец) = R1[(спец=3) & (Шифр группы=2)] В качестве поискового предиката могут выступать { =,<>,>,>=,<= } Операция СОЕДИНЕНИЯ. В отличие от операции ограничения операция бинарна и она определена для двух отношений,для кото- рых на виделенных доменах может быть задан предикат лямда = { =,<>.>,>=,<= } Формально операция записывается в виде : Rрез= R1[(булевское выраж.)]R2 Если лямда есть операция равенства =,то этот частный слу- чай называется операцией эквисоединения. При выполнении операции эквисоединения может возникнуть ловушка соединения,то есть при эквисоединении семантически вер- ных отношений может получиться семантически ложное отношение. ПРИМЕР : Пусть R1(Изготовитель,Цех,Адрес,Деталь) S2 D1 T2 A1 S3 D1 T2 A2 S1 D1 T1 A1 S4 D1 T2 A3 S1 D2 T1 A1 Пусть R2(Изготовитель,Адрес,Деталь) P1 T2 A1 P2 T2 B1 P3 T1 A2 P1 T2 A3 P2 T2 A1 Попытка произвести R1 и R2 по атрибуту Деталь,может при- вести к ложному выводу,т.к. не обязятельно,чтобы потребитель получал все детали от всех изготовителей.Для устранения указан- ного недостатка была предложена ТЕОРИЯ НОРМАЛИЗАЦИИ. Операция ДЕЛЕНИЯ. Пусть имеется отношение R1 (ШD,ШМ),которое показывает,что детали ( атрибут ШD ) могут изготавливаться из некоторых ма- териалов ( атрибут ШМ ). Состояние отношения R1 следующее : R1 ( ШD , ШМ ) R2 ( ШМ ) D1 M2 M5 D2 M5 M9 D2 M9 D3 M2 D3 M5 D2 M3 Пусть задано отношение R2,указывающее,какие материалы хра- нятся на складе.Если к БД поступил запрос,определить детали, которые могут быть изготовлены из ВСЕХ материалов,хранимых на складе,то неформально мы можем определить,что такой деталью яв- ляется только деталь D2,так как она может быть изготовлена как из материала М5,так и из М9. Формально этот запрос соответствует операции деления ре- ляционной алгебры,которая обозначается Rрез(ШD)=R1[ШМЎШМ]R2 Для формального определения операции деления необходимо ввести понятие МНОЖЕСТВО ОБРАЗОВ : Пусть имеется отношение R( B ).Множество атрибутов В пред- ставим совокупностью непересекающихся множеств,то есть В = Х U Y. Тогда множеством образов Qr( X ) эл-та Х проекции R[X] называ- ется такое множество эл-тов У проекции R[У],для которых конка- тенация Х,У является кортежем отношения R. Qr(X) = { y¦y принадлежит R[Y], принадл. R } ПРИМЕР : R(A,B,C) Qr(a1) = {(b1,c1),(b2,c1)} Qr(a2) = {(b1,c2)} a1 b1 c1 a1 b2 c1 a2 b1 c2 Определение операции деления. Пусть R1( A ) и R2( B ) отношения,где А и В наборы атри- бутов этих отношений ( без повторений ). НЕ А - атрибуты от- ношения R1,не вошедшие в набор А. Операция деления ставит в соответствие отношениям R1 и R2 отношение,обозначенное R1[AЎB]R2,кортежи которого являются та- _ кими элементами проекции R1[А],что проекция R2[B] входит в пос- троенные для них множества образов,то есть _ R1[AЎB]R2 = { t¦t принадл. R1[ А ],R2[B] принадл.{y¦y при- надл.R1[A],(t,y) принадл. R1 }} _ А - не A Если R2<>0 и R1=0,то R2[AЎB]R2=0 по определению. Для нашего случая : R1 ( ШD , ШМ ) R2 (ШМ) R1[ШD,ШМЎШМ]R2 = t1 d1 M2 M5 НЕ-А А t2 d2 M5 M9 t3 d2 M9 t4 d3 M2 ¦ t2 (d2,M5) ¦ M2 t5 d3 M5 t= { t3 (d2,M9) y={ M5 t6 d2 M3 ¦ t5 (d3,M5) ¦ M9 M3 Для {y} из {t} удовлетворяют только кортежи t2 и t3. АЛГОРИТМ ОПЕРАЦИИ ДЕЛЕНИЯ. R1[AЎB]R2 = R1[НЕ-А]\((R1[НЕ-А]xR2[B])\R1)[НЕ-А] Старшинство операций: 1) Операции в скобках 2) x, [], \ Рассмотрим алгоритмы на рассмотренном ранее примере R1(ЩD,ШМ),R2(ШМ) 1) R1(НЕ-А] = R1[ШD] d1 d2 d3 2) R2[НЕ-А] x R2[B] = [ШD,ШМ] = R3 d1 M5 R1(ШD ШМ) d1 M9 d2 M5 d1 M2 d2 M9 d2 M5 d3 M5 d2 M9 d3 M9 d3 M2 d3 M5 d2 M3 3) R2[НЕ-А] x R2[B] \ R1 = R3 \R1 = R4(ШD,ШМ) d1 M5 d1 M9 d3 M9 4) В полученном отношении R4 берется проекция по НЕ-А = ШD,то есть получаем R5 R5(ШD) d1 то есть список деталей,которые не могут быть сдела- d3 ны как из материала М5,так и М9. 5) Полученное отношение R5 должно быть вычтено из R1[НЕ-А],т.е. { d1,d2,d3 } \ { d1,d3 } = d2 ЗАКЛЮЧЕНИЕ АЛГЕБРЫ ОТНОШЕНИЙ. Рассмотрим использование алгебры отношений при составле- нии запросов. Пусть БД содержит отношения R1(ШD,ШМ,НР) и R2(ШМ",НМ). Запрос.Перечислить шифры материалов и их наименования (НМ),которые идут на изготовление одной детали в количестве большем,чем 25 кг : Rрез(ШМ,НМ) = ((R1[НР > 25])[ШМ]) [ШМ=ШМ"] R2[ШМ,НМ] Круглые скобки определяют последовательность действий : 1) Ограничение отношения R1 2) Проектирование промежуточного отношения 3) Соединение с R1 4) Проектирование полученного результата Нетрудно видеть,что при таком подходе закладывается " про- цедурность " запроса,поэтому для ЯМД,построенных на алгебре отношений принято говорить как о процедурных языках. Рассмотренная алгебра безусловно имеет преимущества,но требует от пользователя четкого представления ( алгоритма ) вы- полнения операций алгебры,возлагая тем самым на пользователя вопросы эффективности реализации запроса.Указанный недостаток устранен в реляционном исчислении. ПРЕДПОСЫЛКИ ВВЕДЕНИЯ ИСЧИСЛЕНИЯ ОТНОШЕНИЙ. Реляционная алгебра определяет набор операций ( алгебраи- ческих ),которые должны быть реализованы системой для получения ответа на запрос. Взаимодействуя с системой на языке алгебры отноше- ний,пользователь должен уметь манипулировать соответствующими операциями реляционной алгебры при конструировании запросов.При этом от пользователя-непрофессионала требуются определенные знания в области математики и на него же возлагаются вопро- сы,связанные с построением таких запросов на алгебре,которые для своей реализации требовали бы минимальное время. Пусть,например,есть БД,состоящая из следующих отношений : Изделие R1 Цех R2 Цех-изделие -----------------¬ ---------T-------¬--------T-----T-----¬ ¦ шифр ¦ хар-ки ¦ ¦ N цеха ¦ имя ¦¦ N ¦шифр ¦к-во ¦ ¦ изд. ¦ изд. ¦ ¦ ¦ цеха ¦¦ цеха ¦изд. ¦ ¦ ¦----------------¦ +--------+-------++-------+-----+-----+ ¦ Ш1 ¦ Х1 ¦ ¦ N1 ¦ И1 ¦¦ N1 ¦ Ш1 ¦ 10 ¦ ¦ Ш2 ¦ Х2 ¦ ¦ N2 ¦ И2 ¦¦ N1 ¦ Ш2 ¦ 10 ¦ ¦ Ш3 ¦ Х3 ¦ L-----------------¦ N2 ¦ Ш1 ¦ 10 ¦ L----------------- ¦ N2 ¦ Ш2 ¦ 10 ¦ ¦ N2 ¦ Ш3 ¦ 20 ¦ L-------+-----+------ Запрос к базе : Указать шифры цехов,которые изготавливают все детали,вы- пускаемые на данном предприятии. Для реализации данного запроса пользователь может постро- ить несколько предложений на языке алгебры отношений. Например : 1) Rрез(N цеха)=(R3[Nцеха,Шифр изд] х° R2[Nцеха]) Ў R1[Шифр изд] или 2) Rрез(Nцеха)=(R3[Nцеха,Шифр изд]ЎR1[Шифр изд]) х° R2[Nцеха] х° - символ операции эквисоединения При реализации запроса типа 1 или 2 СУБД будет строго при- держиваться порядку операций,предписанных в предложении.При этом существенна в данном случае операция Ў R[AЎB]S=R[НЕ-А]\((R[НЕ-А] х S[B])\R)[НЕ-А], так как она и будет определять время выполнения данного запро- са. Рассмотрим процесс выполнения запроса,для предложения ти- па 1 и типа 2 для нашего примера. ВЫПОЛНЕНИЕ ЗАПРОСА ТИПА 1. Rрез(Nцеха)=(R3[Nцеха,Ш] х° R2[Nцеха] Ў R1[Ш] 1) шаг R4=R3 x° R2 R4 (Nцеха, Ш ) N1 Ш1 N1 Ш2 N2 Ш1 N2 Ш2 N2 Ш3 2) R4ЎR1 = R4[Nц]\((R4[Nц] x R1[Ш])\R4)[Nц] a) R4[Nц] = R5 [Nц] N1 N2 б) R4[Nц] x R1[Ш] = R5 x R1 [Ш]=R6 R6( Nц, Ш ) N1 Ш1 N1 Ш2 N1 Ш3 N2 Ш1 N2 Ш2 N3 Ш3 в) R6 \ R4 = R7 R7 ( Nц, Ш ) N1 Ш3 г) R7[Nц] = {N1} = R8(Nц) д) R4[Nц]\R8 = Rрез = R5\R8 Rрез= N цеха R5(Nц) \ R8(Nц) N2 N1 N1 N2 ВЫПОЛНЕНИЕ ЗАПРОСА ТИПА 2. Rрез(Nц)=(R3[Nц,Ш)]ЎR1[Ш]) x° R2[Nц] 1 шаг:R3[Nц,Ш]ЎR1[Ш] = R3[N4]\((R3[N4] x R1[Ш]) \ R3)[N4] a) R3[Nц] = R4 [Nц] N1 N2 б) R3[Nц] x R2[Ш] = R4 x R3[Ш] = R5( Nц, Ш ) N1 Ш1 N1 Ш2 N1 Ш3 N2 Ш1 N2 Ш2 N2 Ш3 в) R5 \ R3 = R6(Nц, Ш ) N1 Ш3 г) R6[Nц] = {N1} д) R3[Nц]\R6(Nц) = R7 = {N2} e) Rрез = R7(Nц) x° R2[Nц] = R7(Nц) x° R2[Nц] N2 N1 N2 Rрез=N2 Анализ выполнения запросов типа 1 и 2 показывает,что су- щественное влияние на скорость ответа будет оказывать число опе- раций эквисоединения,что в свою очередь определяется уже особен- ностями физической организации .Цель же реляционного подхода - освободить пользователя от физической организации. В основе средств,устраняющих этот недостаток,лежит реля- ционное исчисление.Оно только описывает ( декларирует ) резуль- тат,предоставляя системе решить,какие операции и в какой пос- ледовательности должны быть в действительности выполнены. ФУНКЦИОНАЛЬНЫЕ ЗАВИСИМОСТИ В ОТНОШЕНИЯХ. Реляционная модель учитывает ограничения,накладываемые се- мантикой предметной области на используемые данные.Одним из та- ких ограничений,существующих в предметной области,является по- нятие функциональной зависимости,которое поддается строгой фор- мализации и на основании которого можно правильно спроектиро- вать схему БД.Известно,что реляционная модель БД представляет собой совокупность схем отношений,описы вающих некоторую пред- метную область.С точки зрения реляционного подхода любая пред- метная область может быть описана с помощью только одного стро- ительного блока - отношения,которое покрывает различные поня- тия инфологической модели. Такие понятия,как объект и связь между объектами,представ- лены в реляционной модели одним типовым блоком отношений. Естественно,что такое отношение будет иметь какие-то внутрен- ние ограничения,учитываюособенности моделируемой предметной об- ласти. [ 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) Отношения должны адекватно ( без потерь ) отображать предметную область. 2) Выбранный состав отношений должен удовлетворять мини- мальной избыточности атрибутов,описывающих предметную область. 3) Модель ( состав отношений ) должна быть устойчива при операциях модификации хранимой информации с сохранения требования 1. Рассмотрим указанные требования для схемы отношения Поставщик ( Имя , Адрес, Товар, Цена) И1 А1 Т1 Ц1 И1 А1 Т2 Ц2 И1 А1 Т3 Ц3 И2 А2 Т2 Ц2 И2 А2 Т4 Ц1 1) ИЗБЫТОЧНОСТЬ. Даже для такого маленького r ясно,что Адрес поставщика неоднократно повторяется в отношении. 2) ПОТЕНЦИАЛЬНАЯ ПРОТИВОРЕЧИВОСТЬ ( аномалии обновления ). Если необходимо изменить адрес поставщика,то это не- обходимо делать в нескольких кортежах.Эта проблема воз- никает из-за того,что один и тот же факт ? хранится в нескольких местах. 3) АНОМАЛИЯ ВКЛЮЧЕНИЯ. Если необходимо в отношение доба- вить информацию о поставщике,который в данный момент не поставляет товар,то это сделать не так просто,так как атрибут Товар является ключом отношения. 4) АНОМАЛИЯ УДАЛЕНИЯ. Если удаляется поставщик,то теряет- ся информация,например о стоимости товара. Эти проблемы в значительной мере будут устранены,если ис- ходное отношение будет представлено в виде двух проекций R1(Имя пост, Адрес) и R2(Имя пост,Товар,Цена) При этом исходное отношение будет восстановимо из R1 и R2 с помощью операции эквисоединения по атрибуту Имя поставщи- ка,т.е. R = R1[Имя пост = Имя пост]R2 Для решения правильного построения схемы БД выполняется нормализация исходной схемы,которая опирается на такие поня- тия,как функциональная зависимость и ключ отношения. НОРМАЛЬНЫЕ ФОРМЫ ОТНОШЕНИЙ. Нормальные формы отношений были предложены прежде всего для подавления избыточности данных в базе и устранения побочных эффектов при модификации хранимых данных.Основой для построения нормализованной реляционной модели БД является отношение в ПЕР- ВОЙ НОРМАЛЬНОЙ ФОРМЕ ( 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 ] Отношение находится в 4 НФ,если оно декомпозировано по многозначным зависимостям и только тогда,когда при существова- нии МЗ в R R(ABC) A --->---> B,все атрибуты R также функцио- нально зависят от А. А --->---> В Например R (Курс, Препод, Учебник) Мат Иванов ВМ Мат Иванов Алгебра Физ Петров Оптика Физ Петров Эл-во то есть существует взаимная независимость между Преподавате- лями и Учебниками. ЗАВИСИМОСТИ СОЕДИНЕНИЯ. [ 1 ]. МЗ позволяют разложить исходное отношение на составляю- щие,сохраняя возможность восстановить исходное отношение опе- рацией эквисоединения. Однако исходное отношение может содержать МЗ и ФЗ,но не учитывать некоторые ограничения предметной области. Пусть R (Дет,Мат,Техн) D1 M1 T1 D1 M2 T3 D2 M3 T1 D3 M1 T2 D3 M4 T2 Пусть между объектами Дет и Мат устанавливается связь,ко- торая трактуется как "варианты изготовления деталей из матери- алов". Дет ў Техн трактуется как : для изготовления детали ис- пользуются различные технологии. Мат ў Техн : технология определяется не только типом де- тали,но и используемым материалом. Представленное отношение R находится в 4НФ,т.к. нетриви- альные МЗ отсутствуют,а ключом отношения являются все атрибу- ты.Однако удаление например детали D2 приводит к удалению все- го кортежа,т.к. по определению ключа в нем не может быть неоп- ределенных значений.Т.о.,будет потеряна информация,что техно- логия Т1 использует материал М3. Однако,исходное R может быть представлено следующими про- екциями: R1 ( Дет,Мат ) R2 ( Дет,Техн ) R3 ( Мат,Техн ) D1 M1 D1 T1 M1 T1 D1 M2 D1 T3 M1 T2 D2 M3 D2 T1 M2 T3 D3 M1 D3 T2 M3 T1 D3 M4 M4 T2 И исходное отношение R будет восстановимо из проекций,ес- ли использовать зависимости соединения,которые с помощью неко- торых проекций контролируют истинность операций эквисоединения. Например R' (Дет,Мат,Техн) = R1[ Дет=Дет ]R2 будет содержать лишние кортежи,которые не содержатся в R3,т.е. их надо исключить R(Дет,Мат,Техн) = R'[(Мат=Мат) & (Техн = Техн)]R3 Подобное разложение получило название зависимостей соеди- нения или J зависимостей. МЕТОДЫ И СПОСОБЫ РЕШЕНИЯ ЗАДАЧИ ПО НОРМАЛИЗАЦИИ ОТНОШЕНИЙ. ФОРМАЛЬНАЯ ПОСТАНОВКА ЗАДАЧИ ПРОЕКТИРОВАНИЯ РЕЛЯЦИОННОЙ СХЕМЫ. Пусть задана схема 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 ] ДОСТОИНСТВА И НЕДОСТАТКИ НОРМАЛИЗОВАННОЙ МОДЕЛИ. [ 1 ]. Главной целью процесса нормализации является уменьшение избыточности и,следовательно,в некоторой степени устранения определенных проблем,связанных с проблемами поиска и модифика- ции хранимых данных.Действительно, 4НФ стремится погасить из- быточность,но следует помнить,что совокупность отношений в 4НФ в общем случае полученная из 1 НФ м.б. не единственной,если отношение в 1 НФ имеет не один возможный ключ.Кроме того,ока- зывается не всегда возможно и описать предметную область в ви- де совокупностей в 4 НФ.Поэтому 4 НФ следует рассматривать как методику построения модели данных,которая помогает администра- тору отражать часть семантики реального мира. ТРЕБОВАНИЯ К РАЗРАБАТЫВАЕМОМУ АЛГОРИТМУ. За точку отсчета при разработке алгоритма при приведении отношений к той или иной нормальной форме целесообразно взять таблицу характеристик алгоритмов,которая показывает,что уже бы- ло сделано в области нормализации отношений,процедуру Фэджина, поскольку она единственная,приводящая отношение к 4НФ,а также алгоритм построения замыкания для заданных структур функциона- льных и многозначных зависимостей.Теперь можно будет сформули- ровать требования к разрабатываемому алгоритму. Из анализа таблицы характеристик алгоритмов видно следующее : 1) Разрабатываемый алгоритм должен принимать на входе функциональные зависимости. 2) Разрабатываемый алгоритм должен принимать на входе мно- гозначные зависимости. 3) Разрабатываемый алгоритм должен принимать на входе со- вокупность функциональных и многозначных зависимостей. 4) Разрабатываемый алгоритм должен приводить заданное от- ношение,как минимум,к 3НФ. 5) Разрабатываемый алгоритм желательно сделать более оп- тимальным,чем процедура Фэджина ( вопрос оптимальности в дальнейшем будет подробно рассмотрен ). 6) Желательно,чтобы рассматриваемый алгоритм был как можно более простым ( то есть не включал бы в себя решение NP-полной задачи ),а для этого нужно : a) Перед началом работы основной части алгоритма выяс- нить,находится ли отношение в 3НФ.Причем эту задачу придется решать,как и в процедуре Фэджина,на каждом этапе декомпозиции.Однако выше было сказано,что данная задача являеся NP-полной,если ее решать тра- диционными методами.Следовательно,придется искать принципиально новое решение ( если только оно во- обще возможно ). b) Поскольку поиск возможных ключей заданного отношения тоже является NP-полной задачей,желательно найти та- кой способ разложения,который бы не требовал поис- ка всех возможных ключей отношения,либо же сконст- руировать такой алгоритм поиска возможных ключей ( да и сверхключей тоже ),который был бы значитель- но проще всех существующих.Кроме того,в ходе раз- ложения заданного отношения неоднократно придется решать вопрос,является ли та или иная функциональная или многозначная зависимость ключевой ; поэтому ре- шение данного вопроса должно находиться за одну-три машинные операции. с) Провести тщательную классификацию функциональных и многозначных зависимостей,с тем чтобы рассматривать только такие зависимости,которые нам будут необхо- димы для декомпозиции,то есть необходимо каким-то образом рассматривать не все замыкание,которое может быть получено при использовании аксиом вывода функ- циональных зависимостей,а только его некоторую часть. 7) Из рассмотренных выше требований и пожеланий видно,что при их реализации получится алгоритм,который можно сде- лать основой для программной системы,осуществляющей разложение отношений в 3НФ в диалоговом режиме,причем полученная процедура будет работать гораздо быстрее процедуры Фэджина. СПИСОК ЛИТЕРАТУРЫ. [ 1 ] - КОПЕЙКИН М.В. ЛЕКЦИИ ПО БАЗАМ ДАННЫХ. [ 2 ] - ДРИБАС В.П.РЕЛЯЦИОННЫЕ МОДЕЛИ БАЗ ДАННЫХ.БГУ.МИНСК. БССР.1982 [ 3 ] - Е.А.НЕКЛЮДОВА,М.Ш.ЦАЛЕНКО.СИНТЕЗ ЛОГИЧЕСКОЙ СХЕМЫ РЕ- ЛЯЦИОННЫХ БАЗ ДАННЫХ.ПРОГРАММИРОВАНИЕ,N 6,1979 [ 4 ] - К.ДЕЙТ.ВВЕДЕНИЕ В СИСТЕМЫ БАЗ ДАННЫХ. МОСКВА.НАУКА. 1980. [ 5 ] - Д.ЦИКРИТЗИС.Ф.ЛОХОВСКИ.МОДЕЛИ ДАННЫХ.МОСКВА.ФИНАНСЫ И СТАТИСТИКА.1985 ДОПОЛНИТЕЛЬНАЯ ЛИТЕРАТУРА. 1. ЖЕРНАК А.Н.МЕТОДИЧЕСКИЕ УКАЗАНИЯ ПО КУРСОВОМУ ПРОЕКТИРОВА- НИЮ.СЗПИ.1992 2. ЖЕРНАК А.Н.АЛЕКСАНДРОВ Н.Н.РАБОТА С ДАННЫМИ НА ЭВМ.УЧЕБНОЕ ПОСОБИЕ.СЗПИ.1985