1 ГОУ ВПО Уральский государственный технический университет – УПИ

2 Кафедра «Автоматика и управление в технических системах» направление – Автоматизация и управление специальность – Управление и информатика в технических системах ИНФОРМАЦИОННОЕ ОБЕСПЕЧЕНИЕ СИСТЕМ УПРАВЛЕНИЯ Лекция 9 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами 5.2. Многозначные зависимости Преподаватели: Чесноков Юрий Николаевич, доц., к.т.н., Дружинина Надежда Геннадьевна, доц.

3 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Цель изучения материала: научиться проектировать реляционную модель данных с помощью функциональных и многозначных зависимостей между атрибутами. Компетенций, формирующиеся в процессе знакомства с материалом: готовность учитывать современные тенденции развития информационных технологий в своей профессиональной деятельности (ОНК-2); способность применять современные информационные компьютерные технологии: самостоятельно работать с СУБД (ИК-1); готовность работать с информацией из различных источников (ИК- 4); способность к приобретению новых знаний, используя современные информационные технологии (СЛК-4); способность разрабатывать информационное обеспечение систем с использованием стандартных СУБД (ПКД-5); готовность использовать современные инструментальные средства и технологии проектирования программных средств (ПТД-2); способность составлять техническую документацию на разработку программного обеспечения (ПТД-4).

4 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Содержание лекции 9 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами 5.2. Многозначные зависимости

5 Функциональные зависимости (ФЗ) – определяют все возможные состояния БД, а не текущее состояние. ФЗ отражают связи между атрибутами, присущие реальному объекту, который моделируется с помощью БД. Поэтому ФЗ не всегда можно определить по текущему состоянию БД. Набор ФЗ задает разработчик, системный аналитик, исходя из тщательного анализа предметной области. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

6 Распознавание функциональной зависимости представляет собой часть процесса выяснения смысла тех или иных данных. О взаимоотношении моделей «сущность – связь» и функциональных зависимостей: «… когда решают, чем на самом деле определяется структура БД – ФЗ или сущностями, это напоминает вечный вопрос о том, что было раньше: курица или яйцо. Самое важное – ER-диаграмма и функциональные зависимости, выявленные в отношениях, соответствуют друг другу. Нет никакой разницы в том, как именно проектируется система: анализом функциональных зависимостей или анализом сущностей» [12]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

7 Далее будем использованы следующие обозначения: А, В, С – одиночные атрибуты; X, Y, Z – множество атрибутов; а, в, с,…, x, y, z – значения атрибутов; U, R, S – отношения. U – универсальное отношение (УО), т.е. полный набор атрибутов отношений R, S,… В универсальном отношении каждый атрибут имеет уникальное имя. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

8 Атрибут Y отношения R функционально зависит от атрибута X отношения R, если в каждый момент времени определенному значению х соответствует одно и то же значение y, что обозначают f: X Y и читают либо как «X функционально определяет Y», либо как «X стрелка Y». Левую часть этой символической записи функциональной зависимости называют детерминантом (determinant) или определителем, а правую – зависимой частью. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

9 Обозначение X Y означает, что между X и Y нет функциональной зависимости. Атрибуты взаимно независимы, если каждый из них можно обновлять независимо от значений остальных атрибутов. Если X Y и Y X, то между X и Y взаимно однозначное соответствие, обозначаемое как X Y. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

10 Таблица на рис. 5.1 дает пример функциональной зависимости между атрибутами «Поставщик» и «Страна поставщика». Поставщик «IBM» всегда имеет значение атрибута «Страна поставщика» – США, т.е. одному и тому же значению атрибута «Поставщик» соответствует единственное уникальное значение атрибута «Страна поставщика». 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

11 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами Рис Пример функциональной зависимости ПоставщикИзделияСтрана поставщика IBMКомпьютерСША МерседесАвтомобильГермания IBMМат. платСША

12 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами Другой пример функциональной зависимости между атрибутами показан в таблице на рис. 5.2, из которой очевидно, что функционально зависят атрибуты «Адрес» и «Телефон». Рис Пример ФЗ между атрибутами «Адрес» и «Телефон» ФамилияАдресТелефон СидоровМира, СидороваМира,

13 Для каждого R существует определенное множество ФЗ между его атрибутами. Из одной или более заданных функциональных зависимостей R можно вывести другие ФЗ в этом отношении. Например, дана схема отношения R(A 1, A 2, A 3 ) и в нем заданы функциональные зависимости А 1 А 2 и А 2 А 3. Значит, в нем есть и такие ФЗ: А 1 А 3, А 1 A 2 А 3, А 1 А 2 А 3 А 1 А 2, А 1 А 2 А 2 А 3 и т.д. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

14 Обозначим множество заданных зависимостей F = {А 1 А 2, А 2 А 3 }, а множество F+ = {А 1 А 3, А 1 A 2 А 3, А 1 А 2 А 3 А 1 А 2, А 1 А 2 А 2 А 3, …} – полное множество ФЗ, которое логически следует из F. Множество F+ называется замыканием F. Это замыкание можно найти по правилам вывода или аксиомам ФЗ. При их рассмотрении примем, что даны: схема отношения R(A 1, A 2,..., A m ) на универсальном множестве атрибутов U = {А 1, А 2, А 3, …, A n }; множество исходных ФЗ F = {F 1, F 2, F 3, …, F k }. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

15 Правило Ф1 (свойство рефлексивности). Если X U, Y U, Y X, то ФЗ X Y следует из F. Правило Ф1 дает тривиальные зависимости, т.е. такие, которые не могут не выполняться: A i Ai; A i A j A i ; …………. A i A j A k A l A r A j A k A r и т.д. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

16 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами Пример. Пусть заданы R(A 1, A 2, A 3, A 4, A 5 ), U = (A 1, A 2, A 3, A 4, A 5 ), F = {A 1 A 2, A 1 A 3, A 1 A 4, A 1 A 5 }, конкретный экземпляр отношения R и множество атрибутов Х и Y (рис. 5.3), удовлетворяющих Ф1: X = {A 2, A 4, A 5 }, Y = {А 2, А 5 }. Отношение RАтрибуты X Атрибуты Y A1A1 A2A2 A3A3 A4A4 A5A5 A2A2 A4A4 A5A5 A2A2 A5A5 абавзбвзбз дилгзигзиз едмншдншдш вкасхксхкх Рис Иллюстрация первого правила вывода

17 Из анализа кортежей R следует, что в R есть ФЗ X Y, т.е. {А 2, А 4, А 5 } {А 2, А 5 } – одной и той же совокупности значений по атрибутам множества Х соответствует одна и та же совокупность по атрибутам множества Y. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

18 Из правила Ф1 следует: а) в исходную ФЗ A i A j A k A r A j A k в состав множества атрибутов левой части выражения можно вводить любые атрибуты из U, не нарушая ФЗ; б) можно добавлять атрибуты из U в состав множества атрибутов правой части, если добавленные атрибуты имеются в левой части; в) можно удалять атрибуты из правой части; г) можно удалять атрибуты из левой части, если они отсутствуют в правой. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

19 Правило Ф2 (свойство пополнения). Если X U, Y U, Z U и есть ФЗ X Y, которая либо принадлежит F, либо получена из F с использованием правил вывода, то X Z Y Z, при этом X, Y или Z могут перекрываться или нет. На основании Ф2 можно любые атрибуты из U одновременно подставлять в правую и левую части ФЗ, не нарушая ее. Например, если Х = (А 1 ), Y = (A 3 ), Z = (A 4, A 5 ), то имеется ФЗ X Z Y Z в виде {А 1, А 4, А 5 } {А 3, А 4, А 5 }. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

20 Правило Ф3 (свойство транзитивности). Если X U, Y U, Z U и заданы ФЗ X Y, Y Z, которые либо принадлежат F, либо получены по правилам вывода, то X Z. Перечисленные три правила называют аксиомами Армстронга. Они являются полными и исчерпывающими, так как все остальные правила можно получить на их основе. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

21 Правило Ф4 (свойство расширения). Если X U, Y U и задана ФЗ X Y, то для любого Z U имеется ФЗ Х Z Y. Используя правило Ф1, запишем: Х Z X, так как X Х Z. Если задано, что X Y, то, используя правило Ф3, получим: Х Z Y, так как Х Z X и X Y. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

22 Правило Ф5 (свойство продолжения). Если X U, Y U, W U, Z U и задана ФЗ X Y, то для любых W Z имеет место ФЗ X Z Y W. Поскольку задано, что X Y, то, используя правило Ф2, запишем: X Z Y Z. Используя правило Ф1, запишем Y Z Y W (так как W Z, то, следовательно, Y W Y Z). Используя правило Ф3, окончательно получим: X Z Y W, так как X Z Y Z и Y Z Y W. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

23 Правило Ф6 (свойство псевдотранзитивности). Если X U, Y U, W U, Z U и заданы ФЗ X Y и Y W Z, то имеется ФЗ X W Z. Поскольку задано, что X Y, то, используя правило Ф2, запишем (пополняя по W): X W Y W. Если задано X W Z, то, используя правило ФЗ, окончательно запишем: X W Z, так как X W Y W и X Y Z. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

24 Правило Ф7 (свойство аддитивности или объединения). Если X U, Y U, Z U и заданы ФЗ X Y, X Z, т.е. ФЗ X Y Z. Поскольку задано, что X Y, то, используя правило Ф2, запишем (пополняя по X): X X Y X. Или, если X X = X, то X Y X. Используя зависимость X Z и правило Ф2, запишем (пополняя по Y): X Y Z Y. На основании правила ФЗ и зависимостей X Y X и X Y Z Y следует, что X Y Z. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

25 Правило Ф8 (свойство декомпозиции). Если X U, Y U, Z U и при этом Z Y задана ФЗ X Y, то будет ФЗ X Z. Поскольку задано, что Z Y, то, используя правило Ф1, запишем Y Z. На основании правила Ф3 из зависимостей X Y и Y Z следует: X Z. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.1. Функциональные зависимости между атрибутами

26 Многозначная зависимость – обозначается как (М)Y от X или f: X Y, существует, если при заданных значениях атрибутов из Х имеется множество, состоящее из нуля или более взаимосвязанных значений атрибутов из Y, причем множество значений Y никак не связано со значениями остальных атрибутов отношения, обозначаемых как («R-X-Y»). 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости

27 Таким образом, при многозначной зависимости одному значению некоторого атрибута соответствует устойчиво постоянное множество значений другого атрибута [1]. Для существования в отношении многозначной зависимости необходимо иметь минимум три атрибута: ключ и независимые атрибуты, которых не может быть менее двух (чтобы быть независимыми друг от друга). 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости

28 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости Пример. Проверить наличие многозначной зависимости YZ в заданном отношении R (рис. 5.4). Отношение R Название кортежаXYZ tавс vавд ежз uшвс sшвд Рис Пример многозначной зависимости

29 Выберем в отношении R кортежи t и s (t:, s: ), для которых t[Y] = s[Y] = в – значения атрибута Y равны. По значениям этих компонентов формируем кортежи u и v: 1) u[Y] = v[Y] = t[Y] = s[Y] = в; 2) u[Z] = t[Z] = c, u[X] = s[X] = ш; 3) v[Z] = s[Z] = д, v[X] = t[X] = a. Из этих равенств следует, что в отношении R должны быть следующие кортежи u: и v:, что и имеет место. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости

30 Общее правило гласит: если в R имеется зависимость XY, то для двух произвольных кортежей t и s, таких что t[X] = s[X], отношение обязательно содержит кортежи u и v такие, что выполняются условия: 1) u[X] = v[X] = t[X] = s[X]; 2) u[Y] = t[Y], u[R-X-Y] = s[R-X-Y]; 3) v[Y] = s[Y], v[R-X-Y] = t[R-X-Y]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости

31 Если поменять местами значения атрибутов Y в кортежах t и s, то можно получить два кортежа u и v, которые также должны принадлежать рассматриваемому отношению. Можно дать такую формулировку: многозначная зависимость существует, если каждому значению атрибута A соответствует конечное множество значений атрибута B, связанных с A, и конечное множество значений атрибута C, также связанных с A. Атрибуты B и C друг от друга не зависят [12]. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости

32 Многозначные зависимости всегда образуют связанные пары. В [12] написано, что, говоря точнее, функциональная зависимость – это многозначная зависимость особого рода, когда определяется одно значение, а не группа. Пример отношения из области работы следователей с многозначной зависимостью приведен на рис ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости

33 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости Рис Пример отношения с многозначной зависимостью ОперацияФамилияМероприятие «Ы»Пронин«Прыжок» «Ы»Пронин«Бросок» «Золотой глаз»Бонд«Подход» «Золотой глаз»Бонд«Контакт» «Золотой глаз»Бонд«Связь»

34 На основе этого отношения в [5] дано другое определение многозначной зависимости. В отношении с атрибутами X, Y, Z существует многозначная зависимость атрибута Y от X (XY) тогда и только тогда, когда любое значение из множества Y, соответствующее паре значений X и Z, зависит только от значения Y. 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости

35 В отношении на рис. 5.5 имеется «Операция»«Фамилия», так как для любой пары значений («Операция», «Мероприятие») значение атрибута «Фамилия» определяется только значением атрибута «Операция». Аналогично имеется многозначная зависимость «Операция»«Мероприятие». 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД 5.2. Многозначные зависимости

36 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Выводы и заключение по лекции: научились проектировать реляционную модель данных с помощью функциональных и многозначных зависимостей между атрибутами.

37 5. ПРОЕКТИРОВАНИЕ РЕЛЯЦИОННЫХ БД Перечень источников: Четвериков В.Н. Базы и банки данных/ В.Н. Четвериков, Г.И. Ревунков, Э. Н. Самохвалов; под ред. В.Н. Четверикова. М.: Высшая школа, с. Дейт К. Дж. Руководство по реляционной СУБД DB2/ К. Дж. Дейт. М.: Финансы и статистика, с. Дейт К. Дж. Введение в системы баз данных/ К. Дж. Дейт. М.: Издательский дом «Вильямс», 2001, 1072 с. Дмитриев В.И.Прикладная теория информации/В.И. Дмитриев. М.:Высшая школа, с. Гайдамакин Н.А. Автоматизированные информационные системы, базы и банки данных/ Н.А. Гайдамакин. М.: Гелиос АРВ, С. Карпова Т.С. Базы данных: модели, разработка, реализация/ Т.С. Карпова. СПб.: Питер, с. Мамаев Е.В. MS SQL Server 7.0. Проектирование и реализация баз данных/ Е.В. Мамаев. СПб.: БХВ-Санкт-Петербург, с. Озкарахан Э. Машины баз данных и управление базами данных/ Э. Озкарахан. М.: Мир, с. Селко Джо. SQL для профессионалов. Программирование/ Джо Селко. М.:«Лори», с. Системы управления базами данных и знаний/ А.Н. Наумов [и др.]; под общ. ред. А.Н. Наумова. М.: Финансы и статистика, с. Теория автоматического управления/ С.Е. Душин [и др.]; под общ. ред. Б. Б. Яковлева. М.: Высшая школа, с. Харрингтон Дж. Л. Проектирование реляционных баз данных. Просто и доступно/ Дж. Л. Харрингтон. М.: «Лори», с. Хендерсен К. Delphi 3 и системы клиент/сервер: руководство разработчика/ К. Хендерсен. Киев: Диалектика, с.