Учебное пособие по базам данных. Учебное пособие. Пособие по базам данных Введение
 Скачать 169.5 Kb.
|
|
Определение. Пусть Ri[A1, …, Am] и Rj[B1, ..., Bp] – схемы отношений (не обязательно различные), V {A1, …, Am} и W {B1, ..., Bp}, |V|=|W|, тогда объект Ri[V] Rj[W] называется зависимостью включения, если V(Ri) W(Rj). В определении |V| – мощность множества V, V(Ri) – проекция отношения Ri по атрибутам V. Условие V=W является необходимым для установления связи. Такой вид зависимостей включения называется типизированными. Это дополнительное ограничение вполне согласуется с общепринятым свойством связей на схеме БД: связи отражают количественное соотнесение кортежей в отношениях и не обладают какой-либо семантикой. Необходимость связывания различных по смыслу атрибутов, скорее всего, является признаком потери какой-либо функциональной зависимости для связываемых атрибутов, либо, зависимость включения устанавливается для атрибутов-синонимов. То есть, решение семантических проблем на предварительном этапе проектирования схемы базы данных в большинстве случаев позволяет избавиться от необходимости использования нетипизированных зависимостей включения. Введем обозначения: PK(Ri) или просто PK(i) – множество атрибутов, являющихся первичным ключом в отношении Ri; L1(i,j) – связь 1:1 от Ri к Rj, где Ri главное отношение; LM(i,j) – связь 1:M от Ri к Rj, где Ri главное отношение; L(i,j) – связь 1:1 либо 1:M от Ri к Rj, где Ri главное отношение. Определение. Между отношениями Ri и Rj существует связь L1(i,j), если PK(Ri)=PK(Rj) и для любых реализаций Ri и Rj, выполнено X(Rj)X(Ri), где X=RiRj. Определение. Между отношениями Ri и Rj существует связь LM(i,j), если PK(Ri)PK(Rj) и PK(Ri)Rj. Заметим, что ограничение целостности, задаваемое связью LM(i,j) подразумевает V(Rj)V(Ri), где V= RiRj. Определение. Связь L(i,j) является избыточной, если задаваемые ею ограничения на значения атрибутов содержатся в других связях. Утверждение. Связь L(i,j) является избыточной, если и только если существуют связи: L(i,m(1)), L(m(1),m(2)), …, L(m(p-1),m(p)), L(m(p),j) (1) и PK(i)Rm(s), s=2,3,…,p, (2) где m – массив номеров отношений. Следствие. Если существует (1) и p=1, то связь L(i,j) избыточна. Замечание. Последовательность нескольких связей не может быть избыточна. Допустим, что существуют последовательности (1) и L(i,v), L(v,j), vm(s), s=1,2,…,p. Удаление связей L(i,v) и L(v,j), независимо от условия (2), означало бы снятие ограничений с отношения Rv, накладываемых связью L(i,v). Поиск избыточных связей с использованием приведенных соотношений (1) и (2) является экспоненциальной задачей. Поскольку связи являются реализацией типизированных зависимостей включения, то к поиску избыточных связей применим алгоритм построения замыкания отношений, являющийся полиномиальным по времени, где L – множество всех связей и Ri+ - замыкание отношения Ri. Проверяем на избыточность связь L(i,j): Шаг 0. Ri+=Ri (рефлексивность зависимостей включения). Шаг i (i=1,2,..). Выполняется итерация: просматриваются все связи L(v,w)L. Если для текущей связи Rv Ri+ и w=j, то связь L(v,w) избыточна (конец алгоритма). Если RvRi+, wj и RwRi+, то выполняем подстановку: Ri+=Ri+Rw. Если после выполнения одной итерации не было сделано ни одной подстановки, то связь L(i,j) не является избыточной (конец алгоритма), в противном случае переход к следующей итерации. С учетом того, что на каждой итерации к замыканию присоединяется не менее одного отношения (их k штук), рассмотренный алгоритм будет иметь полиномиальную сложность. Этап 4. Составить три запроса к БД в терминах реляционной алгебры, используя форму универсального реляционного запроса: запрос с обобщенным ключом, запрос без обобщенного ключа, запрос на вычитание. Совокупность отношений, входящих в запросы, должна локально удовлетворять свойству соединения без потерь информации. Провести формальную оптимизацию запросов, используя свойства операций реляционной алгебры. Этап 5. Сформировать описание физического представления данных, определив перечень основных файлов БД. Определить типы записей в основных файлах, типы и размеры полей для записей каждого типа. Определить наиболее подходящий метод доступа для каждого файла. Замечание. При выборе метода доступа необходимо учитывать частоту обращения к файлу, типы индексируемых полей, частоту модификации записей файла, устойчивость к программным и аппаратным сбоям и т.д. Результаты выполнения данного и следующего этапов должны явиться основанием для выбора СУБД. Этап 6. Провести анализ особенностей реализации информационной системы, обратив особое внимание на детали работы приложений со схемой БД. Пример Рассмотрим прикладную область "Чемпионат по футболу" Перечень исходных документов: "Турнирная таблица", "Заявки команд на матч", "Судейский протокол", "Продажа билетов на матч". Для сокращения объема примера опустим другие сведения, например, "Назначение судейской бригады на матч", "Обслуживающий персонал стадиона" и т.д. Заметим, что правильное построение схемы БД позволит дополнить эту информацию без разрушения уже построенной схемы. Этап 1. Общий перечень элементов данных (атрибутов). Список расширен номерами объектов, для которых отсутствует однозначная идентификация в прикладной области (команды, игры и т.д.). 1. Номер матча. 2. Номер команды хозяев матча. 3. Номер команды гостей матча. 4. Наименование команды. 5. Номер игрока в команде. 6. Номер члена команды. 7. Роль члена команды {тренер, защитник, массажист …}. 8. Номер стадиона. 9. Название стадиона. 10. Город расположения стадиона. 11. Номер игрового события в матче. 12. Время игрового события. 13. Номер игрока, участвующего в игровом событии. 14. Номер команды игрока, участвующего в игровом событии. 15. ФИО игрока. 16. ФИО члена команды. 17. Название игрового события {гол, игра рукой …}. 18. Номер зрительской трибуны. 19. Номер ряда на трибуне. 20. Номер места в ряду на трибуне. Анализируем элементы данных на предмет наличия синонимов и омонимов. Элементы 2 и 3 синонимы. Заменяем их парой элементов: 2. Номер команды. 3. Статус команды в матче {гость, хозяин}. Это наиболее распространенная ошибка при проектировании, когда роль или функцию объекта выделяют в отдельный атрибут. Например, "ФИО водителя", "ФИО диспетчера" и т.д., тогда как нужны два атрибута: "ФИО сотрудника" и "Должность сотрудника". Элементы 5 и 6 частично дублируют друг друга. Уточним семантику элемента 5 "Игровой номер футболиста" (номер на футболке). После этого преобразования элемент 13 становится синонимом элемента 5. Элемент 13 удаляется. Аналогично элемент 14 является синонимом номера команды. Элементы 15 и 16 являются синонимами, причем элемент 16 имеет большую область определения, он и останется в перечне. Результирующий перечень элементов данных следующий: 1. Номер матча. 2. Номер команды. 3. Статус команды в матче {гость, хозяин}. 4. Наименование команды. 5. Игровой номер футболиста. 6. Номер члена команды. 7. Роль члена команды {тренер, защитник, массажист …}. 8. Номер стадиона. 9. Название стадиона. 10. Город расположения стадиона. 11. Номер игрового события в матче. 12. Время игрового события. 13. ФИО члена команды. 14. Название игрового события {гол, игра рукой …}. 15. Номер зрительской трибуны. 16. Номер ряда на трибуне. 17. Номер места в ряду на трибуне. Дополнительные атрибуты: 18. Номер названия игрового события. 19. Дата проведения матча. 20. Время проведения матча. Этап 2. Для выделенных элементов строим множество функциональных зависимостей, используя обратный метод: 1, обозначает, что первый элемент функционально ничем не определяется функциональная зависимость отсутствует; 21,11; 31,2, если зафиксирован номер матча и номер команды, то статус команды в матче будет иметь точно одно значение; 42; 51,11; 62,5, если зафиксирован игровой номер футболиста, то номер члена команды будет иметь точно одно значение, в обратную сторону зависимости нет: не все члены команды являются футболистами; 72,6; 81; 98; 108, не рекомендуется различными наименованиями определять другие элементы: зависимости 109 нет; 11; 121,11; 132,6; 141,11, хотя эта зависимость выполнена, ввод названия события всякий раз при фиксации события является трудоемким и чреват множеством ошибок, пронумеруем эти названия, дав возможность реализовать выбор из меню уже введенных названий; 1418; 15; 16; 17; 181,11; 191; 201. Построив минимальное покрытие множества функциональных зависимостей, получим, что зависимость 1,1114 является избыточной. Этап 3. Строим каноническую модель данных реляционного типа, удовлетворяющую свойству соединения без потерь информации и сохраняющую зависимости. Объединяем зависимости с одинаковой левой частью. Результирующее множество имеет следующий вид: 1,23; 24; 1,112,5,12,18; 2,56; 2,67,13; 18,19,20; 89,10; 1814. Из полученных зависимостей формируем отношения, присваивая им наименования и подчеркивая ключевые элементы данных (первичные ключи отношений). R1=Статусы команд в матчах
R2=Команды
R3=Игровые события
R4=Распределение игровых номеров
R5=Списочный состав команд
R6=Расписание матчей
R7=Стадионы
R8=Справочник игровых событий
Обобщенный ключ следующий: 1. Номер матча. 11. Номер игрового события в матче. 15. Номер зрительской трибуны. 16. Номер ряда на трибуне. 17. Номер места в ряду на трибуне. Отношение, сформированное для обобщенного ключа, имеет вид
Полученное отношение имеет приемлемую содержательную интерпретацию, однако совершенно не технологично. Действительно, при регистрации очередного игрового события оператор должен дублировать сведения о нем для всех проданных билетов на матч. Это, в свою очередь, является признаком наличия многозначной зависимости. Зависимость имеет вид |