МИНИСТЕРСТВО ОБРАЗОВАНИЯ РОССИЙСКОЙ ФЕДЕРАЦИИ КРАСНОЯРСКАЯ ГОСУДАРСТВЕННАЯ АКАДЕМИЯ ЦВЕТНЫХ МЕТАЛЛОВ И ЗОЛОТА Кафедра ПМ и АСУ Группа ИС-01-1 Дисциплина Базы и банки знаний Пояснительная записка к курсовой работе Тема Автоматизация проектирования реляционных баз данных синтез В-схемы Студенты Булахов А.С. Павлов К.А. Засыпалов
И.Ю. Зырянов Д.Ф. Руководитель работы Быкова В.В. Красноярск 2004 СОДЕРЖАНИЕ Введение 1. Постановка задачи1. Технологические аспекты работы2. Требования к отладке программ. Распределение работ.2. Описание пакета программ 1. Входные и выходные данные2. Состав и функции пакета программ.3. Эксплутационные характеристики и особенности пакета.10 2.4.
Решение практической задачи вручную 5. Решение практической задачи с помощью разработанного пакета программ16 Заключение19 Список литературы 20 Приложение. Текст программы КГАЦМиЗ. УП000.069.ПЗ Лист2Изм.Лист докум.ПодписьДата ВВЕДЕНИЕ Данная курсовая работа служит закреплением практических и теоретических знаний, полученных при изучении дисциплины Базы и банки знаний.
Цели работы Детальное изучение основных алгоритмов теории нормализации, связанных с автоматизацией проектирования реляционных баз данных. Реализация алгоритмов в виде пакета программ, позволяющего осуществить синтез схемы реляционной базы данных с заданными свойствами, исходя из F-описания описания предметной области на языке функциональных зависимостей. Использование разработанного пакета программ для решения реальной практической задачи.
Приобретение навыков коллективной работы по созданию программного продукта и решению практических задач. КГАЦМиЗ. УП000.069.ПЗ Лист 3Изм.Лист докум.ПодписьДата 1. ПОСТАНОВКА ЗАДАЧИ 1.1 ТЕНОЛОГИЧЕСКИЕ АСПЕКТЫ РАБОТЫ Известно, что база данных БД динамически обновляемая информационная модель предметной области, а процесс е проектирования процесс моделирования предметной области. Результатом моделирования предметной области является, прежде всего, логический проект БД схема БД. В рамках реляционного подхода схема БД дает ответы на следующие вопросы Ш сколько таблиц должно быть в БД, Ш какие атрибуты содержит каждая таблица, Ш каковы ключи таблиц Физическое проектирование БД доводка логического проекта с учетом особенностей выбранной СУБД и требований к эксплуатационным характеристикам
БД. Эта доводка включает в себя такие действия Ш установление явных связей между таблицами, Ш определение индекса таблиц, Ш определение запоминающих устройств, методов доступа, способов защиты и т.д. Ясно, что основная задача проектировщика БД получение хорошего логического проекта БД. Исходными данными для решения этой задачи являются Ш множество атрибутов, значения которых требуется хранить в
БД Ш множество связей между атрибутами. Прежде чем приступить к выработке проектных решений по структуризации данных требуется выразить описать семантическую структуру предметной области. Для этих целей существует несколько систем нотаций систем условных обозначений, языков. Наиболее распространнные системы нотаций Ш модель сущность – связь ER-модель. Семантическая структура предметной области представляется
ER-диаграммой Ш язык функциональных зависимостей ФЗ. Семантическая структура предметной области представляется F-описанием – множеством ФЗ F. Научиться синтезировать схему реляционной БД, исходя из F описания основная цель данной курсовой работы. Рассмотрим проблемы, возникающие при синтезе схемы
БД и алгоритмические способы решения этих проблем. КГАЦМиЗ. УП000.069.ПЗ Лист4Изм.Лист докум.ПодписьДата Проблема 1 неизбыточность представления F-описания. Для всякой предметной области можно построить несколько эквивалентных F-описаний. Можно ли, опираясь на некоторое исходное F-описание заданной предметной области, найти для F эквивалентное неизбыточное представление представление, лишенное избыточных ФЗ и посторонних атрибутов Ответ положительный, для этого существуют соответствующие алгоритмы чистки F-описания. Чистка исходного F-описания выполняется в два этапа 1. вначале из F удаляются все избыточные ФЗ они логически следуют из оставшихся. Полученное в результате множество ФЗ называют неизбыточным покрытием
F и обозначают Fнеизб 2. далее из Fнеизб удаляются посторонние атрибуты. Этот процесс называется редуцированием, а полученное в результате множество ФЗ называется редуцированным покрытием и обозначается Fред. Множество ФЗ Fред. не всегда является самым экономным оптимальным представлением семантической структуры предметной области. Тем не менее, использование
Fред. для синтеза схемы БД обеспечивает в достаточной мере неизбыточность получаемой БД. Проблема 2 оценка качества проектных решений. Известно, что к организации БД предъявляются три требования правило Три НЕ неизбыточность, непротиворечивость, независимость. Последнее из них независимость данных от приложений достигается в основном средствами СУБД. Неизбыточность и непрворечивость БД можно обеспечить путм выбора подходящей схемы
БД. В теории нормализации доказано, что БД будет неизбыточной и средствами СУБД можно достичь е непротиворечивого состояния, если е схема будет эффективной относительно заданного F-описания предметной области. Пусть R множество имен атрибутов, значения которых требуется хранить в БД, и F множество ФЗ, описывающих связи между атрибутами. Схема БД над R называется эффективной относительно
F, если 1 она сохраняет F разбиение R на R1, R2 Rm не приводит к потере зависимостей из F, а значит, связей между атрибутами КГАЦМиЗ. УП000.069.ПЗ Лист5Изм.Лист докум.ПодписьДата 2 обладает свойствами соединения без потерь информации представления БД в виде одной таблицы rR или в виде совокупности таблиц r1R1, r2R2 rmRm равносильны. Последнее означает, что любое допустимое состояние таблицы rR всегда можно получить из таблиц r1R1, r2R2 rmRm с помощью операции естественного соединения кК к1К1 к2К2 кьКь 3 все подсхемы Ri с нормализованы, то есть находятся в НФБКнормальной форме Бойса Кодда. Это означает, что всякая ФЗ, действующая в рамках таблицы riRi в левой части имеет ключ таблицы riRi, i 1, 2 m. Теорема. Для любого множества ФЗ F, заданного на конечном множестве атрибутов R, всегда существует схема
БД обладающая свойством соединения без потерь, сохраняющая все ФЗ из F и находящаяся в 3НФ. Схему БД, удовлетворяющую условиям данной теоремы, принято называть В-схемой. Свойства В-схемы вполне приемлемы для практики, так как они гарантируют непротиворечивость БД. 3НФ допускает определнное избыточное дублирование данных, но с этим приходится мириться и учитывать в программах ввода и редактирования данных. Данная курсовая работа предполагает программную реализацию
процесса синтеза В-схемы, указанного на рис. 1 КГАЦМиЗ. УП000.069.ПЗ Лист6Изм.Лист докум.ПодписьДата 1.2. ТРЕБОВАНИЯ К ОТЛАДКЕ ПРОГРАММ. РАСПРЕДЕЛЕНИЕ РАБОТ Все работы, связанные с разработкой пакета программ, решением практической задачи и оформлением результатов курсовой работы, были распределены между студентами исполнителями
Исполнитель 1 Павлов Константин Исполнитель 2 Засыпалов Илья Исполнитель 3 Зырянов Дмитрий Исполнитель 4 Булахов Александр Объм всех работ разделн на четыре задания. Учитывая сложность алгоритмов, распределение работы по заданиям было выполнено согласно рис. 2 КГАЦМиЗ. УП000.069.ПЗ Лист7Изм.Лист докум.ПодписьДата
КГАЦМиЗ. УП000.069.ПЗ Лист8Изм.Лист докум.ПодписьДата 2. ОПИСАНИЕ ПАКЕТА ПРОГРАММ 2.1. ВХОДНЫЕ И ВЫХОДНЫЕ ДАННЫЕ Входными данными в пакете программ являются Ш Множество имн атрибутов Ш Множество функциональных зависимостей. Внутренне представление данных указано в табл. 1. В процессе работы пакета программ формируется В схема с указанием ключей для каждой таблицы БД. 2.2. СОСТАВ И ФУНКЦИИ ПАКЕТА ПРОГРАММ Пакет реализован на языке Object Pascal в объектно-ориентированной среде Delphi 7.0, которая предоставляет широкий набор средств, позволяющих быстро и эффективно разрабатывать программы, предназначенные для создания и обслуживания Базы данных. Процедуры и функции пакета программ представлены в таблице 2. Таблица 2 Наименование процедур и функций Назначение процедур и функций
Procedure TForm1.ButAtrClick Ввод атрибутов Procedure TForm1.ButfuncClick Ввод ФЗ Procedure TForm1.ProvercaClick Проверка выводимости Procedure TForm1.ButposizbClick Построение неизбыточного покрытия Procedure TForm1.ButposredClick Построение редуцированного покрытия Procedure TForm1.ButkeyClick
Нахождение ключа Procedure TForm1.ButpostabloClick Прогонка табло Procedure TForm1.ButpossintezClick Синтез B-схемы КГАЦМиЗ. УП000.069.ПЗ Лист9Изм.Лист докум.ПодписьДата 2.3. ЭКСПЛУТАЦИОННЫЕ ХАРАКТКРИСТИКИ И ОСОБЕННОСТИ ПАКЕТА Для функционирования пакета программ требуются технические средства
Ш IBM PC на базе микропроцессора Pentium 200 и выше Ш Видеоадаптер VGA Ш Свободного дискового пространства не менее 600 Кб Ш Клавиатура Ш Манипулятор типа мышь. КГАЦМиЗ. УП000.069.ПЗ Лист10Изм.Лист докум.ПодписьДата 2.3. РЕШЕНИЕ ПРАКТИЧЕСКОЙ ЗАДАЧИ ВРУЧНУЮ Состав атрибутов практической задачи приведн в табл.
3 Таблица 3 Имя атрибута Семантика A Номер рейса N Пункт назначения S Тип самолета M Количество посадочных мест D1 Дата вылета D2 Время вылета P1 Код пилота командира экипажа P2 Ф.И.О. пилота T Длительность полета Описание предметной области на языке ФЗ приведено в табл. 4. Таблица 4 Функциональная зависимость
Семантика P1 P2 Код однозначно идентифицирует пилота A ND2 Номер рейса однозначно определяет пункт назначения и время вылета AD1D2 P1P2S Для каждого рейса на определенный день вылета назначается командир экипажа и тип самолета SN TM Длительность полета и количество посадочных мест определяются типом самолета и пунктом назначения D1D2P1 A Пилот одновременно пилотирует только один рейс AD1 T Длительность полета зависит от номера рейса, даты вылета КГАЦМиЗ. УП000.069.ПЗ Лист11Изм.Лист докум.ПодписьДатаЗаданы множество атрибутов R A, N, S, M, D1, D2, P1, P2, T с семантикой A – номер рейса N – пункт назначения S – тип самолета M – количество посадочных мест D1 – дата вылета D2 – время вылета P1 – код пилота командира экипажа
P2 – Ф.И.О. пилота T – длительность полета множество функциональных зависимостей FP1 P2, A ND2, AD1D2 P1P2S, SN TM, D1D2P1 A, AD1 T с семантикой P1 P2 код однозначно идентифицирует пилота A ND2 номер рейса однозначно определяет пункт назначения и время вылета AD1D2 P1P2S для каждого рейса на определенный день вылета назначается командир экипажа и тип самолета SN TM длительность полета и количество посадочных мест определяются типом самолета и
пунктом назначения D1D2P1 A пилот одновременно пилотирует только один рейс AD1 T длительность полета зависит от номера рейса, даты вылета. Решение 1. Построение неизбыточного покрытия. Для построения неизбыточного покрытия необходимо удалить избыточные ФЗ. Для этого вычислим замыкания для каждой ФЗ P1 P1 A A AD1D2 AD1D2NT SN SN D1D2P1 D1D2P1 AD1
AD1ND2P1P2STM AD1 AD1ND2P1P2STM данная ФЗ избыточна, т. к. она определяет атрибут Т через ФЗ AD1 T, следовательно, мы е удаляем из F. Получаем FP1 P2, A ND2, AD1D2 P1P2S, SN TM, D1D2P1 A КГАЦМиЗ. УП000.069.ПЗ Лист12Изм.Лист докум.ПодписьДата 2. Построение редуцированного покрытия. Для построения редуцированного покрытия необходимо из левых и правых
частей ФЗ удалить посторонние атрибуты. Редуцирование левых частей Fлев. ред. P1 P2, A ND2, AD1D2 P1P2S, SN TM, D1D2P1 A. Редуцирование правых частей Fправ. ред. P1 P2, A ND2, AD1 P1P2S, SN TM, D1D2P1 A. В результате Fред. P1 P2, A ND2, AD1 P1S, SN TM, D1D2P1 A. 3. Нахождение ключа. Для этого в Fред. введм фиктивную ФЗ ANSMD1D2P1P2T X. После этого Fред. редуцируем, просматривая ФЗ в произвольном порядке Fред P1 P2, A ND2, AD1 P1S, SN TM, D1D2P1 A, ANSMD1D2P1P2T X . Следовательно, ключ – AD1D2. Здесь есть ещ один ключ D1D2P1. 4. Разложение множества атрибутов по функциональным зависимостям.
Выполним синтаксическое разложение R по ФЗ из Fред В результате имеем сR1 P1 P2, R2 A ND2, R3 AD1 P1S, R4 SN TM, R5 AD1D2P1. 5. Прогонка табло. Проверим свойство соединения без потерь методом прогонки табло. КГАЦМиЗ. УП000.069.ПЗ Лист13Изм.Лист докум.ПодписьДата Метод прогонки табло завершился успешно, т. к. в табло имеются две строки выделенных переменных 3 и 5
строки .Это означает, что с обладает свойством соединения без потерь и не будет ловушек соединений ответы на запросы будут всегда верны. 6. Результаты синтеза. Таким образом результатом синтеза является B- схема, которая имеет вид сR1 P1 P2, R2 A ND2, R3 AD1 P1S, R4 SN TM, R5 AD1D2P1. Данная схема по построению сохраняет все ФЗ из F и обладает свойством соединения без потерь.
Это гарантирует для БД ее непротиворечивость. Семантика таблиц базы данных со схемой с такова r1R1 Список пилотов r2R2 Характеристика рейсов r3R3 График полтов номер рейса дата вылета код пилота командира экипажа тип самолета A D1 P1 S r4R4 Характеристика маршрутов тип самолета пункт назначения длительность полета количество посадочных мест S N T M r5R5 График загрузки пилотов номер рейса дата вылета время вылета код пилота командира экипажа A D1 D2 P1 КГАЦМиЗ.
УП000.069.ПЗ Лист14Изм.Лист докум.ПодписьДата Проверка нормальной формы для с R1, R2, R3, R4, R5 F1 P1 P2 r1R1 в НФБК. F2 A ND2 r2 R2 в НФБК F3 AD1 P1S r3R3 в НФБК. F4 SN TM r4R4 в НФБК. F5 D1D2P1 A, AD1 P1 r5R5 в 3 нормальной форме. Так как AD1 P1 частичная функциональная зависимость, AD1 часть ключа AD1D2, в правой части данной зависимости имеется ключевой атрибут P1. В таблице график загрузки пилотов r5R5 возможно избыточное дублирование данных, так как она находится в 3 нормальной форме, в связи с этим е нужно аккуратно обновлять, чтобы не допустить избыточности. Все остальные таблицы в НФБК, следовательно, в них нет избыточного дублирования данных. КГАЦМиЗ. УП000.069.ПЗ Лист15Изм.Лист докум.ПодписьДата 2.4.
РЕШЕНИЕ ПРАКТИЧЕСКОЙ ЗАДАЧИ С ПОМОЩЬЮ РАЗРАБОТАННОГО ПАКЕТА ПРОГРАММ 1. Экран ввода с исходными данными задачи 6. Построение замыкания КГАЦМиЗ. УП000.069.ПЗ Лист16Изм.Лист докум.ПодписьДата7. Построение не избыточного покрытия 8. Построение редуцированного покрытия 9. Нахождение ключа
БД 10. Метод прогонки Табло КГАЦМиЗ. УП000.069.ПЗ Лист17Изм.Лист докум.ПодписьДата 11. Синтез B схемы Результаты синтеза полученные с помощью пакета программ и вручную совпадают. КГАЦМиЗ. УП000.069.ПЗ Лист18Изм.Лист докум.ПодписьДата ЗАКЛЮЧЕНИЕ Группой студентов был разработан программный продукт для автоматизации проектирования реляционных баз данных. Он основан на применении алгоритмов построения схемы базы данных
с использованием функциональных зависимостей, описывающих заданную предметную область. Данная программа может быть использована в учебном процессе по дисциплине Базы и банки данных для наглядного изучения способов и примов проектирования баз данных. КГАЦМиЗ. УП000.069.ПЗ Лист19Изм.Лист докум.ПодписьДата