Автоматизация проектирования реляционных баз данных: синтез В-схемы

СОДЕРЖАНИЕ

Введение…………………………………………………………..…………3

1. Постановка задачи……………………………………………………5

   1. Технологические аспекты работы……………………………5

   2. Требования к отладке программ. Распределение работ….…7

2. Описание пакета программ…………………………………………..9

   1. Входные и выходные данные…………………………………9

   2. Состав и функции пакета программ…………………….……9

   3. Эксплутационные характеристики и особенности пакета….10

   4. Решение практической задачи вручную……………………..11

   5. Решение практической задачи с помощью разработанного пакета программ…………………………………………………16

Заключение…………………………………………………………………19

Список литературы………………………………………………………...20

Приложение. Текст программы

КГАЦМиЗ. УП000.069.ПЗ

Лист

2

Изм.

Лист

№ докум.

Подпись

Дата

ВВЕДЕНИЕ

Данная курсовая работа служит закреплением практических и теоретических знаний, полученных при изучении дисциплины “Базы и банки знаний”.

Цели работы:

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

• Реализация алгоритмов в виде пакета программ, позволяющего осуществить синтез схемы реляционной базы данных с заданными свойствами, исходя из F-описания (описания предметной области на языке функциональных зависимостей).

• Использование разработанного пакета программ для решения реальной практической задачи.

• Приобретение навыков коллективной работы по созданию программного продукта и решению практических задач.

КГАЦМиЗ. УП000.069.ПЗ

Лист

3

Изм.

Лист

№ докум.

Подпись

Дата

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 на R₁, R₂, …, R_m не приводит к потере зависимостей из F, а значит, связей между атрибутами);

КГАЦМиЗ. УП000.069.ПЗ

Лист

5

Изм.

Лист

№ докум.

Подпись

Дата

1. обладает свойствами соединения без потерь информации (представления БД в виде одной таблицы r(R) или в виде совокупности таблиц r₁(R₁), r₂(R₂), …, r_m(R_m) равносильны). Последнее означает, что любое допустимое состояние таблицы r(R) всегда можно получить из таблиц r₁(R₁), r₂(R₂), …, r_m(R_m) с помощью операции естественного соединения

к(К) = к₁(К₁) к₂(К₂) … к_ь(К_ь)

3) все подсхемы R_i? нормализованы, то есть находятся в НФБК(нормальной форме Бойса–Кодда). Это означает, что всякая ФЗ, действующая в рамках таблицы r_i(R_i) в левой части имеет ключ таблицы r_i(R_i), i =1, 2, …, m.

Теорема. Для любого множества ФЗ F, заданного на конечном множестве атрибутов R, всегда существует схема БД

обладающая свойством соединения без потерь, сохраняющая все ФЗ из F и находящаяся в 3НФ.

Схему БД, удовлетворяющую условиям данной теоремы, принято называть В-схемой. Свойства В-схемы вполне приемлемы для практики, так как они гарантируют непротиворечивость БД. 3НФ допускает определённое избыточное дублирование данных, но с этим приходится мириться и учитывать в программах ввода и редактирования данных.

Данная курсовая работа предполагает программную реализацию процесса синтеза В-схемы, указанного на рис. 1

КГАЦМиЗ. УП000.069.ПЗ

Лист

6

Изм.

Лист

№ докум.

Подпись

Дата

1.2. ТРЕБОВАНИЯ К ОТЛАДКЕ ПРОГРАММ. РАСПРЕДЕЛЕНИЕ РАБОТ

Все работы, связанные с разработкой пакета программ, решением практической задачи и оформлением результатов курсовой работы, были распределены между студентами – исполнителями:

Исполнитель 1 – Павлов Константин

Исполнитель 2 – Засыпалов Илья

Исполнитель 3 – Зырянов Дмитрий

Исполнитель 4 – Булахов Александр

Объём всех работ разделён на четыре задания. Учитывая сложность алгоритмов, распределение работы по заданиям было выполнено согласно рис. 2

КГАЦМиЗ. УП000.069.ПЗ

Лист

7

Изм.

Лист

№ докум.

Подпись

Дата

Исполнитель 1

Задание 1

Разработка и отладка

• модуля ввода,

• модуля проверки выводимости,

• модуля построения неизбыточного покрытия.

Решение вручную практической задачи согласно варианту.

Исполнитель 2

Задание 2

Разработка и отладка

• модуля 1 редуцирования,

• модуля 2 редуцирования.

Решение вручную практической задачи согласно варианту.

Исполнитель 3

Задание 3

Разработка и отладка:

• модуля прогонки табло.

Решение вручную практической задачи согласно варианту.

Оформление пояснительной записки, материалы к которой предоставляют все другие исполнители.

Исполнитель 4

Задание 4

Разработка и отладка:

• модуля синтеза,

• головного модуля.

Решение вручную практической задачи согласно варианту.

Координация, планирование и контроль исполнения заданий.

КГАЦМиЗ. УП000.069.ПЗ

Лист

8

Изм.

Лист

№ докум.

Подпись

Дата

НАЗВАНИЕ ПОЛЯ

ТИП ПОЛЯ

Атрибуты

ФЗ

Левая часть ФЗ

Правая часть ФЗ

Строковый

Массив множеств

Множество

Множество

1. ОПИСАНИЕ ПАКЕТА ПРОГРАММ

2.1. ВХОДНЫЕ И ВЫХОДНЫЕ ДАННЫЕ

Входными данными в пакете программ являются:

• Множество имён атрибутов;

• Множество функциональных зависимостей.

Внутренне представление данных указано в табл. 1.

В процессе работы пакета программ формируется В – схема с указанием ключей для каждой таблицы БД.

2.2. СОСТАВ И ФУНКЦИИ ПАКЕТА ПРОГРАММ

Пакет реализован на языке Object Pascal в объектно-ориентированной среде Delphi 7.0, которая предоставляет широкий набор средств, позволяющих быстро и эффективно разрабатывать программы, предназначенные для создания и обслуживания Базы данных. Процедуры и функции пакета программ представлены в таблице 2.

Таблица 2

КГАЦМиЗ. УП000.069.ПЗ

Лист

9

Изм.

Лист

№ докум.

Подпись

Дата

2.3. ЭКСПЛУТАЦИОННЫЕ ХАРАКТКРИСТИКИ И ОСОБЕННОСТИ ПАКЕТА

Для функционирования пакета программ требуются технические средства:

• IBM PC на базе микропроцессора Pentium 200 и выше;

• Видеоадаптер VGA;

• Свободного дискового пространства не менее 600 Кб;

• Клавиатура;

• Манипулятор типа «мышь».

КГАЦМиЗ. УП000.069.ПЗ

Лист

10

Изм.

Лист

№ докум.

Подпись

Дата

2.3. РЕШЕНИЕ ПРАКТИЧЕСКОЙ ЗАДАЧИ ВРУЧНУЮ

Состав атрибутов практической задачи приведён в табл. 3

Таблица 3

Описание предметной области на языке ФЗ приведено в табл. 4.

Таблица 4

КГАЦМиЗ. УП000.069.ПЗ

Лист

11

Изм.

Лист

№ докум.

Подпись

Дата

Заданы: множество атрибутов

R= {A, N, S, M, D₁, D₂, P₁, P₂, T}

с семантикой

A - номер рейса;

N - пункт назначения;

S - тип самолета;

M - количество посадочных мест;

D₁ - дата вылета;

D₂ - время вылета;

P₁ - код пилота – командира экипажа;

P₂ - Ф.И.О. пилота;

T - длительность полета;

множество функциональных зависимостей:

F={P₁? P₂, A? ND₂, AD₁D₂ ? P₁P₂S, SN ? TM, D₁D₂P₁ ? A, AD₁ ? T}

с семантикой

P₁? P₂ – код однозначно идентифицирует пилота;

A? ND₂ – номер рейса однозначно определяет пункт назначения и время

вылета;

AD₁D₂ ? P₁P₂S – для каждого рейса на определенный день вылета

назначается командир экипажа и тип самолета;

SN ? TM – длительность полета и количество посадочных мест

определяются типом самолета и пунктом назначения;

D₁D₂P₁ ? A – пилот одновременно пилотирует только один рейс;

AD₁ ? T – длительность полета зависит от номера рейса, даты вылета.

Решение:

1. Построение неизбыточного покрытия.

Для построения неизбыточного покрытия необходимо удалить избыточные ФЗ. Для этого вычислим замыкания для каждой ФЗ:

(P₁)⁺ = P₁

(A)⁺ = A

(AD₁D₂)⁺ = AD₁D₂NT

(SN)⁺ = SN

(D₁D₂P₁)⁺ = D₁D₂P₁

(AD₁)⁺ = AD₁ND₂P₁P₂STM

(AD₁)⁺ = AD₁ND₂P₁P₂STM – данная ФЗ избыточна, т. к. она определяет атрибут Т через ФЗ AD₁ ? T, следовательно, мы её удаляем из F.

Получаем:

F={P₁? P₂, A? ND₂, AD₁D₂ ? P₁P₂S, SN ? TM, D₁D₂P₁ ? A}

КГАЦМиЗ. УП000.069.ПЗ

Лист

12

Изм.

Лист

№ докум.

Подпись

Дата

1. Построение редуцированного покрытия.

   A

   b₁

   P₁

   P₂

   N

   D₁

   D₂

   S

   T

   M

   a₁

   
   

   a₂

   b₈

   
   

   a₃

   
   

   b₉

   b₂

   
   

   b₃

   
   

   b₄

   a₄

   a₆

   b₅

   
   

   b₆

   
   

   b₇

   b₁₁

   b₁₂

   
   

   b₁₃

   
   

   

Для построения редуцированного покрытия необходимо из левых и правых частей ФЗ удалить посторонние атрибуты.

Редуцирование левых частей:

F_{лев. ред.} = {P₁? P₂, A? ND₂, AD₁D₂ ? P₁P₂S, SN ? TM, D₁D₂P₁ ? A}.

Редуцирование правых частей:

F_{прав. ред.} = {P₁? P₂, A? ND₂, AD₁? P₁P₂S, SN ? TM, D₁D₂P₁ ? A}.

В результате:

F_ред. = {P₁? P₂, A? ND₂, AD₁? P₁S, SN ? TM, D₁D₂P₁ ? A}.

1. Нахождение ключа.

Для этого в F_ред. введём фиктивную ФЗ ANSMD₁D₂P₁P₂T ? X. После этого

F_ред. редуцируем, просматривая ФЗ в произвольном порядке:

F_ред = { P₁? P₂, A? ND₂, AD₁? P₁S, SN ? TM, D₁D₂P₁ ? A, ANSMD₁D₂P₁P₂T ? X }.

Следовательно, ключ - AD₁D_2. Здесь есть ещё один ключ: D₁D₂P₁.

1. Разложение множества атрибутов по функциональным зависимостям.

Выполним синтаксическое разложение R по ФЗ из F_ред.. В результате имеем:

?={R₁ (P₁ P₂), R₂ (A ND₂), R₃ (AD₁ P₁S), R₄ (SN TM), R₅ (AD₁D₂P₁)}.

1. Прогонка табло.

   P₁ P₂

   A ND₂

   AD₁P₁S

   SN TM

   AD₁D₂P₁

   a₁

   b₁₉

   a₁

   
   

   a₂

   
   

   b₂₀

   
   

   a₂

   
   

   b₁₀

   b₁₄

   a₃

   
   

   b₁₅

   a₄

   
   

   a₅

   b₁₆

   a₆

   a₇

   b₂₁

   a₄

   
   

   b₂₂

   b₂₃

   b₁₇

   a₈

   
   

   b₁₈

   a₉

   
   

   a₇

   a₈

   
   

   a₉

   
   

   b₂₈

   a₉

   
   

   
   

   b₂₄

   a₃

   
   

   
   

   b₂₅

   a₄

   
   

   a₅

   
   

   a₆

   
   

   b₂₆

   a₇

   
   

   b₂₇

   a₈

   
   

Проверим свойство соединения без потерь методом прогонки табло.

КГАЦМиЗ. УП000.069.ПЗ

Лист

13

Изм.

Лист

№ докум.

Подпись

Дата

Метод прогонки табло завершился успешно, т. к. в табло имеются две строки выделенных переменных (3 и 5 строки) .Это означает, что ? обладает свойством соединения без потерь и не будет ловушек соединений (ответы на запросы будут всегда верны).

код пилота – командира экипажа

Ф.И.О.

пилота

P₁

P₂

номер рейса

пункт назначения

время вылета

A

N

D₂

6. Результаты синтеза.

Таким образом результатом синтеза является B- схема, которая имеет вид:

?={R₁ (P₁ P₂), R₂ (A ND₂), R₃ (AD₁ P₁S), R₄ (SN TM), R₅ (AD₁D₂P₁)}.

Данная схема по построению сохраняет все ФЗ из F и обладает свойством соединения без потерь. Это гарантирует для БД ее непротиворечивость. Семантика таблиц базы данных со схемой ? такова:

r₁(R₁ ) – Список пилотов

r2(R2 ) – Характеристика рейсов

r₃(R₃ ) – График полётов

r₄(R₄ ) –Характеристика маршрутов

r₅(R₅ )– График загрузки пилотов

КГАЦМиЗ. УП000.069.ПЗ

Лист

14

Изм.

Лист

№ докум.

Подпись

Дата

Проверка нормальной формы для ?= {R₁, R₂, R₃, R₄, R₅}

F₁ ={P₁? P₂} ------------------------- r₁(R₁) – в НФБК.

F₂ ={A? ND₂}----------------------- r₂ (R₂) – в НФБК

F₃ ={AD₁? P₁S } -------------------- r₃(R₃) – в НФБК.

F₄ = {SN ? TM } -------------------- r₄(R₄) – в НФБК.

F₅ = { D₁D₂P₁ ? A, AD₁? P₁}----- r₅(R₅) – в 3 нормальной форме. Так как AD₁? P₁ частичная функциональная зависимость, AD₁ – часть ключа AD₁D₂, в правой части данной зависимости имеется ключевой атрибут P₁.

В таблице график загрузки пилотов r₅(R₅ ) возможно избыточное дублирование данных, так как она находится в 3 нормальной форме, в связи с этим её нужно аккуратно обновлять, чтобы не допустить избыточности. Все остальные таблицы в НФБК, следовательно, в них нет избыточного дублирования данных.

КГАЦМиЗ. УП000.069.ПЗ

Лист

15

Изм.

Лист

№ докум.

Подпись

Дата

ЗАКЛЮЧЕНИЕ

Группой студентов был разработан программный продукт для автоматизации проектирования реляционных баз данных. Он основан на применении алгоритмов построения схемы базы данных с использованием функциональных зависимостей, описывающих заданную предметную область. Данная программа может быть использована в учебном процессе по дисциплине «Базы и банки данных» для наглядного изучения способов и приёмов проектирования баз данных.

КГАЦМиЗ. УП000.069.ПЗ

Лист

19

Изм.

Лист

№ докум.

Подпись

Дата