С.Д. Кузнецов - Основы баз данных (1121716), страница 23
Текст из файла (страница 23)
Элементы теории реляционных баз данных: функциональные зависимости и декомпозиция без потерь Эта и две следующие лекции посвящены вопросам теории реляционных баз данных. Поскольку все направление реляционного подхода к организации баз данных является сугубо практическим, эта теория, главным образом, прагматическая. Основная проблема, на решение которой направлена теория реляционных баз данных, состоит в обнаружении полезных свойств некоторых схем баз данных и выработке способов построения таких схем. Принято кратко назыввгь зту проблему проблемой нрвектированияреляцивнныхбаз данных. Ключевые слова: теория реляционных баз данных, проектирование реляционных баз данных, функциональная зависимость, многозначная зависимость, зависимость соединения, детерминант, тривиальная функциональная зависимость, замыкание множества функциональных зависимостей, транзитивная функциональная зависимость, правила вывода функциональных зависимостей, аксиомы Армстронга, замыкание множества атрибутов над множеством функциональных зависимостей, суперключ отношения, покрытие множества функциональных зависимостей, минимальное множество функциональных зависимостей, минимальное покрытие множества функциональных зависимостей, декомпозиция без потерь, теорема Хита, минимально зависимые атрибуты, диаграммы функциональных зависимостей.
Введение Несмотря на свою практическую ориентированность, теория реляционных баз данных является самостоятельным научным направлением, в котором работали (и продолжают работать) многие известные исследователи, чьи имена будут встречаться в наших лекциях. Мы не планировали в данном курсе подробно описывать основные результаты в области теории реляционных баз данных. Наша цель состоит в том, чтобы обеспечить только определения и утверждения, необходимые для общего понимания процесса проектирования реляционных баз данных на основе нормализации.
Поскольку наиболее важные с практической точки зрения свойства реляционных баз данных базируются на понятии функциональной зависимости, мы выделили в отдельную лекцию краткое обсуждение соответствующих теоретических вопросов. Среди этих вопросов наибольший интерес представляют замыкания и покрытия множеств функциональных зависимостей, аксиомы Армстронга и теорема Хита ыо Лекция 6 Функциональные зависимости и декомпозиция бвз поте ь о достаточном условии декомпозиции отношения без потерь.
Понятия и утверждения данной лекции действительно нужны для усвоения материала лекции 7, но мы стремились еше и пролемонстрировать читателям на несложных примерах, что собой представляет теория реляционных баз данных, каков уровень ее сложности и насколько она понятна интуитивно. Заметим, что мы не вьщеляли в отлельные лекции теоретический материал, касающи йся многозначных зависимостей и зависимостей соединения. Это было сделано по двум причинам. Во-первых, эти виды зависимостей реже встречаются при моделировании предметной области средствами баз данных. Поэтому мы сочли достаточным представить внутри лекции 8 только основы соответствующего теоретического материала.
Во-вторых, хотя теория многозначных зависимостей и зависимостей соединения, по сути, не намного сложнее теории функциональных зависимостей, ее определения и утверждения слишком громоздки для данного курса. Функциональные зависимости Наиболее важные с практической точки зрения нормальные формы отношений основываются на фундаментальном в теории реляционных баз данных понятии функциональной зависимости.
Для дальнейшего изложения нам потребуется несколько определений и утверждений (по ходу изложения мы будем пояснять их и иллюстрировать). Общие определения Пусть задана переменная отношения г, и х и к являются произвольными подмножествами заголовка г (»составными» атрибутами). Определение 6.1. Функциональная зависимость В значении переменной отношения г атрибут у функционально зависит от атрибута хв том и только в том случае, если каждому значению хсоответствует в точности одно значение у. В этом случае говорят также, что атрибут х функционально определяет атрибут к(хявляется детерминантом (определителем) для у, а уявляется зависимым от х).
Будем обозначать это как г. х г. к Конец определения. Для примера будем использовать отношение слукавил пноккты (слу ном, слу имя, слу элпп, про ном, пуоккт рук) (рис. 6.1).Очевидно, что если слу ном является первичным ключом отношения слллщик, то для этого отношения справедлива функциональная зависимость (Гцпсйопа1 Ререпт)епсу — ГР) слу ном слу имя. На самом деле, для тела отношения слуллдик ппоккты в том виде, в котором оно показано на рис. б.1, выполняются еще и следующие ГР (1): 111 Основы бвз данных Куро Рис. 6.1.
Пример возможного тела отношения служлл(ие ЛРОекты ГЛУ НОМ СЛУ ИМЯ СЛУ НОМ СЛУ ЗАРП СЛУ НОМ ПРО НОМ СЛУ НОМ ПРОЕКТ РУК (ГЛУ НОМ, СЛУ ИМЯ) СЛУ ЗАРП (ГЛУ НОМ, ГЛУ ИМЯ) ПРО НОМ (СЛУ НОМ, СЛУ ИМЯ) (СЛУ ЗАРП, ПРО НОМ) ПРО НОМ ПРОЕКТ РУК и тд. Поскольку имена всех служащих различны, то выполняются и такие Г)3 (2): СЛУ ИМЯ СЛУ НОМ СЛУ ИМЯ СЛУ ЗАРП СЛУ ИИЯ ПРО НОМ и т.д.
Более того, для примера на рис. 6.1 выполняется и Г)) (3): СЛУ ЗАРП ПРО НОМ Однако заметим, что природа НЭ группы (1) отличается от природы ГП групп (2) и (3). Логично предположить, что идентификационные номера служащих должны быть всегда различны, а у каждого проекта имеется только один руководитель. Поэтому Г1) группы (1) должны быть верны для любого допустимого значения переменной отношения СЛУЖАШИЕ ПРОЕКТЫ И мОГУт рассматриваться как инварианты, или ограничения Иелосаности этой переменной отношения. Г)3 группы (2) базируются на менее естественном предположении о том, что имена всех служащих различны. Это соответствует действительности для примера из рис.
6.1, но возможно, что с течением времени ГП 1!2 Функциональные зависимости и декомпозиция без потерь Лекция б группы (2) не будут выполняться для какого-либо значения переменной отношения СлужАЩИЕ пРОЕкты. Наконец, ГО группы (3) основана на совсем неестественном предположении, что никакие двое служащих, участвующие в разных проектах, не получают одинаковую зарплату. Опять же, данное предположение верно для примера из рис. 6Л, но, скорее всего, это случайное совладение. В дальнейшем нас будут интересовать только те функциональные зависимости, которые должны выполняться для всех возможных значений переменных отношений.
Заметим, что если атрибут А отношения г является возможным ключом, то для любого атрибута в этого отношения всегда выполняется н) А в(в группе ()) к этим ГГ) относятся все нз, детерминантом которых является СЛУ НОИ). Обратите внимание, что наличие в отношении служАЩие ЛРОекты НЭ пРО ном ПРОект РУк приводит к некоторой избыточности этого отношения. Имя руководителя проекта является характеристикой проекта, а не служащего, но в нашем случае содержится в теле отношения столько раз, сколько служащих работает над проектом.
Итак, мы будем иметь дело с ГР, которые выполняются для всех возможных состояний тела соответствующего отношения и могут рассматриваться как ограничения целостности. Как показывает (неполный) список (!), таких зависимостей может быть очень много. Поскольку они трактуются как ограничения целостности, за их соблюдением должна следить СУБД. Поэтому важно уметь сократить набор ГР до минимума, поддержка которого гарантирует выполнение всех зависимостей. Мы займемся этим в следующих подразделах. Определение 6.2.
Тривиальная функциональная зависимость Н) А В называется тривиальной, если А~В (т. е. множество атрибутов А включает множество в или совпадает с множеством в). Конец определения. Очевидно, что любая тривиальная ГР всегда выполняется. Например, в отношении СЛУЖАЩИЕ ПРОЕКТЫ всегда выполняется Н) (слу ЗАРП, ПРО ПОИ) СЛУ ЗАРП.
Частным случаем тривиальной НЭ является А- А. Поскольку тривиальные НЭ выполняются всегда, их нельзя трактовать как ограничения целостности, и поэтому они не представляют интереса с практической точки зрения. Однако в теоретических рассуждениях их наличие необходимо учитывать. Замыкание множества функциональных зависимостей. Аксиомы Армстронга. Замыкание множества атрибутов Определение 6.3. Замыкание множества г Р Замыканием множества Н) в является множество РР в, включающее все ГР, логически выводимые из ГР множества в.
Конец определения. ОЗ курс Основы баз данных Для начала приведем два примера ГР, из которых следуют (или выводявзся) другие ГР. Будем снова пользоваться отношением служлжие проекты. Для этого отношения выполняется, например, ГР слу ном [слу зАРП, про ном). Из этой ГР выводятся ГР СЛУ НОМ СЛУ ЗАРП и СЛУ НОМ ПРО НОМ. В отношении служйжие проекты имеется также пара ГР слУ ном пРО ном и пРО ном пРОект РУк. Из них выводится ГР слу ном пРОект Рук. Заметим, что ГР вида слУ ном пРОект РУк называются транзитивными, поскольку проект Рук зависит от слу ном етраиэнтИВНО», ЧЕРЕЗ ПРО НОМ. Определение б.4.
Транзптпвпая функциональная зависимость ГР А с называется транзитивной, если существует такой атрибут в, что имеются функциональные зависимости А В и В С и отсутствует функциональная зависимость С- А. Конец определения. Подход к решению проблемы поиска замыкания ь' множества ГР В впервые предложил Вильям Армстронг*. Им был предложен набор правил вывода новых ГР из существующих (эти правила обычно называют аксиомами Армслгронга, хотя справедливость правил доказывается на основе определения ГР). Обычно принято формулировать эти правила вывода в следующей форме. Пусть А, в и с являются (в общем случае, составными) атрибутами отношения г.
Множества А, В и С могут иметь непустое пересечение. Для краткости будем обозначать через Ав А лпон в. Тогда: 1) если ВЯА, то А В (рефлексивность); 2) если А в, то Ас-вс(пополнение); 3) если А в и в с, то А с (транзитивность). Истинность первой аксиомы Армстронга следует из того, что при во=А Н) А вявляется тривиальной. Справедливость второй аксиомы докажем от противного. Предположим, что ГР АС ВС не соблюдается.
![](https://s.studizba.com/z.php?f=/templates/si/i/noavatar.png&w=100&h=100&t=1"){kind=avatar}
