Библиографический список. Пример выполнения задания № 10

Пример выполнения задания № 10

Пример выполнения задания № 9

Пример выполнения задания № 8

Пример выполнения задания № 7

Пример выполнения задания № 6

Пример выполнения задания № 5

Пример выполнения задания № 4

Пример выполнения задания № 3

Пример выполнения задания № 2

Пример выполнения задания № 1

Даны ограничения на данные.

1. На выставке представлены картины многих художников.

2. Каждый художник мог выставить на выставке только одну картину.

3. На выставке не было картин, авторами которых было бы несколько художников.

4. Несколько картин могли иметь одно и то же название.

5. Имена художников уникальны.

6. Для каждой картины была объявлена ее номинальная стоимость.

7. Одну и ту же стоимость могут иметь несколько картин.

Задача. Определить схему отношения и все функциональные зависимости, имеющие место на схеме отношения. Выявить ключи отношения.

Решение:

Выделим все основные сущности, о которых идет речь в данном примере.

· Художник

· Картина

· Выставка.

Атрибуты являются свойствами данных объектов, поэтому на следующем этапе идентифицируем эти свойства (см. Таблица 43).

Таблица 43

	Сущность	Свойства (атрибуты)
1.	Художник	Имя художника
2.	Картина	Название картины
		Номинальная стоимость
	Выставка	? Название выставки

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

Таким образом, в отношении могут иметь место только 3 атрибута, которые и составят схему отношения R={Имя художника, Название картины, Номинальная стоимость}.

Установим функциональные зависимости между атрибутами:

Имя художника®Название картины (на основании 2 и 5 ограничений).

Имя художника®Номинальная стоимость (на основании 2, 5, 6).

Ключом отношения является Имя художника, так как от этого атрибута зависят все остальные атрибуты в отношении. Окончательная схема отношения будет иметь вид:R={ Имя художника, Название картины, Номинальная стоимость}.

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

F₁={№ заказ-наряда ® Имя закройщика};

F₂= {Имя закройщика ® Категория закройщика}.

Задача.

1. Установить внешние ключи отношений в представленных отношениях.

2. Сформулировать ограничения на данные, согласно которым были установлены приведенные функциональные зависимости.

Решение:

Установим схемы отношений:

Cхема первого отношения r₁: R₁(r₁) = { № заказ-наряда, Имя закройщика}.

Схема второго отношение r₂: R₂(r₂) = { Имя закройщика, Категория закройщика}.

Первичные ключи на схемах подчеркнуты.

Первое отношение является ссылающимся, поскольку содержит внешний ключ Имя закройщика. Второе отношение является ссылочным, поскольку имеет в качестве первичного ключа атрибут Имя закройщика.

Из первой функциональной зависимости следует:

1) Номер заказ-наряда уникален.

2) Каждый заказ-наряд выписывается на имя одного закройщика.

3) На имя одного закройщика может быть выписано несколько заказ-нарядов (нет обратной функциональной зависимости).

Вторая функциональная зависимость может иметь место, если:

· Имя закройщика уникально.

· Каждый закройщик имеет только одну категорию.

· Одна и та же категория может быть у нескольких закройщиков (отсутствует обратная функциональная зависимость).

Дано множество функциональных зависимостей {А®С, АC®D, D®E}, имеющих место на схеме R={A,B,C,D,E}.

Задача. Вывести функциональную зависимость А®E двумя способами, используя b - аксиомы и аксиомы Армстронга. Определить ключи отношения.

Решение:

Выведем функциональную зависимость А®E, используя аксиомы Армстронга (см. Таблица 44).

Таблица 44

№	Функциональные зависимости	Основание
1.	А®С	Дано
2.	АC®D	Дано
3.	А®D	Псевдотранзитивность (из 1,2)
4.	D®E	Дано
5.	А®E	Транзитивность (из 3, 4)

Выведем функциональную зависимость А®E, используя β-аксиомы (см. Таблица 45).

Таблица 45

№	Функциональные зависимости	Основание
1.	А®A	Рефлексивность (β1)
2.	А®C	Дано
3.	А®AC	Накопление (β2)
4.	AC®D	Дано
5.	А®ACD	Накопление (β2)
6.	D®E	Дано
7.	А®ACDE	Накопление (β2)
8.	А®E	Проективность (β3)

Из вывода следует и замыкание атрибута А: А+ = {ACDE}.

Aтрибут А есть ключ отношения, так как замыканием А является вся схема отношения, и у ключа нет собственного подмножества.

Дано множество функциональных зависимостей {А®С, АC®DB, D®E}, имеющих место на схеме отношения. Схема отношения полностью определена атрибутами, входящими в данные функциональные зависимости.

Задача. Вычислить каноническое и минимальное покрытие на схеме отношения.

Решение:

Запишем исходное множество функциональных зависимостей в виде таблицы (см. Таблица 46).

Таблица 46

№	Функциональные зависимости
	А®С
	АC®D
	АС®B
	D®E

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

Последовательно удалим “лишние” атрибуты. Так как функциональная зависимость А®D следует из 1, 2 функциональных зависимостей по аксиоме F6 и в то же время АС®D следует из А®D на основании аксиомы F2,то в результате мы можем заменить функциональную зависимость АС®D на А®D (см. Таблица 47).

Таблица 47

№	Функциональные зависимости
	А®С
	А®D
	АC®B
	D®E

Аналогично рассуждая, произведем замену функциональной зависимости АC®B на А®B (см. Таблица 48).

Таблица 48

№	Функциональные зависимости
	А®С
	А®D
	А®B
	D®E

Новое покрытие имеет вид: F_к.п. = {А®С, А®D, А®B, D®E} и является каноническим (обозначение - F_к.п.), оно эквивалентно исходному, так как все функциональные зависимости исходного отношения могут быть получены из вновь полученного путем реализации аксиом вывода.

Минимальное покрытие (F_мп) получим, применив аксиому аддитивности (F3) к первым трем функциональным зависимостям.

В итоге имеем: F_м.п. = {А®СDB, D®E}.

Дано множество функциональных зависимостей F={A®B; CB®A}, атрибуты, входящие в них, полностью формируют схему отношения.

Задача. Определить ключи отношения.

Решение:

Воспользуется b - аксиомами вывода для определения замыканий множеств, состоящих из атрибутов левых частей функциональных зависимостей (см. Таблица 49).

Таблица 49

№	Вывод	Основание		№	Вывод	Основание
	A®A	b1			CB®CB	b1
	A®B	Дано			CB®A	Дано
	A®AB	b2			CB®ABC	b2
	A^+={AB}				CB^+={ABC}

№	Вывод	Основание		№	Вывод	Основание
1.	AC®AC	b1		1.	AB®AB	b1
2.	A®B	Дано		2.	A®B	Дано
3.	A®ABC	b2		3.	AB®AB	b2
	AC^+={ABC}				AB^+={AB}

Из осуществленных выводов очевидно, что AC⁺=BC⁺={АВС}=R. Так как замыканием для АС и ВС является вся схема отношения, то они удовлетворяют первому требованию к ключу, то есть идентифицируют любую запись в отношении. Остается проверить, не содержат ли они внутри себя другого идентификатора. Как показал предыдущий вывод, замыкание атрибута A не эквивалентно схеме отношения, а атрибуты В и С в отдельности определяют только сами себя. Таким образом, исходное отношение имеет 2 ключа: AC и ВС.

Дано отношение со схемой R={ABCDE} и множеством функциональных зависимостей на этой схеме F={AB®C; C®D}.

Задача. Нормализовать отношение до 2НФ. Выявить аномалии во вновь полученных отношениях, если они имеют место. Обосновать причину этих аномалий. Показать пути их устранения.

Решение:

Отношение не находится во 2НФ, так как ключом этого отношения является множество атрибутов {ABE}[6]. Следовательно, атрибуты С и D зависят только от части ключа - атрибутов АВE.

Для приведения отношения во 2НФ выделим всю цепочку функциональных зависимостей, начинающуюся с АВ в отдельное отношение.

В результате образуется два отношения R1={ABE} и R2={ABCD}. Оба отношения будут находиться во 2НФ, однако второе отношение не свободно от избыточного дублирования. Избыточное дублирование будет наблюдаться на атрибуте D, так как он транзитивно зависит от множества атрибутов АВ. Исключить аномалию можно путем декомпозиции второго отношения на 2 отношения: R2={ABC}, R3={CD}.

Дано отношение со схемой R={АBC} и множество функциональных зависимостей на этой схеме F= {АB®C, C®B}.

Задача. Нормализовать отношение до НФБК. Указать, на каких атрибутах в исходном отношении может ожидаться избыточное дублирование.

Решение:

Исходное множество функциональных зависимостей является минимальным, поэтому приступаем непосредственно к этапу декомпозиции, убедившись предварительно в ее необходимости.

Ключом данного отношения будут АВ и АС, т.к. АВ⁺ = АС⁺ =R= {АBC}(см. Таблица 50 и Таблица 51).

Очевидно, что С⁺ ≠ АС⁺, С⁺ = {СB}, а у всех остальных атрибутов замыкание состоит только из самого атрибута.

Таблица 50

№	Функциональные зависимости	Основание
	АВ®АВ	Рефлексивность (β1)
	А®C	Дано
	АB®AВC	Накопление (β2)

Таблица 51

№	Функциональные зависимости	Основание
	АC®АC	Рефлексивность (β1)
	C®B	Дано
	АC®AВC	Накопление (β2)

Выделим в отношении ключи и детерминанты (см. Таблица 52).

Таблица 52

Детерминанты	Ключи
АB	АВ
C	AC

Отношение не находится в НФБК, поскольку множества детерминантов и ключей не эквивалентны. Следовательно, отношение нуждается в декомпозиции.

Выделение функциональной зависимости С®A в отдельное отношение не даст желаемого результата, поэтому применим для декомпозиции теорему Хеза.

В результате получим два отношения со схемами R(r₁)={ АC } и R(r₂) ={ C B}.

Как выделенное, так и оставшееся отношение будут находиться в НФБК. Соотношение детерминант и ключей в отношении r₁ приведено ниже (см. Таблица 53).

Таблица 53

Детерминанты	Ключи
АС	АС

В отношении r₂ также будет наблюдаться полное соответствие между множеством ключей и детерминант (см. Таблица 54).

Таблица 54

Детерминанты	Ключи
С	С

В исходном отношении избыточное дублирование следовало ожидать на атрибуте B, так как он зависел от собственного подмножества возможного ключа АС.

Дано множество функциональных зависимостей на схеме отношения, которая полностью определена атрибутами, входящими в функциональные зависимости.

F={№ лифта ® № дома, Индивидуальный номер слесаря, Имя слесаря, Дата последнего обслуживания;

Индивидуальный номер слесаря ® Имя слесаря;

№ лифта, № дома ® Дата последнего обслуживания, Индивидуальный номер слесаря}.

Задача. Найти минимальное покрытие для отношений, на схеме которых имеют место приведенные ниже функциональные зависимости. Определить ключи исходного отношения. Выполнить декомпозицию без потерь до НФБК. Во вновь полученных отношениях определить первичные, возможные и внешние ключи.

Решение:

В исходном множестве функциональная зависимость № 3 является избыточной, она следует из первой на основании аксиомы F₂ (Пополнение).

Первая функциональная зависимость нередуцированная справа, т.к. содержит “лишний” атрибут: Имя слесаря. Исключив “лишний” атрибут и избыточную функциональную зависимость, имеем:

F={№ лифта ® Индивидуальный номер слесаря, № дома, Дата последнего обслуживания; Индивидуальный номер слесаря ® Имя слесаря}.

Ключом исходного отношения является: № лифта.

Отношение не находится в НФБК (см. Таблица 55).

Таблица 55

Детерминанты	Ключи
№ лифта	№ лифта
Индивидуальный номер слесаря

Приводим исходное отношение в НФБК, выделив каждую функциональную зависимость в отдельное отношение.

В результате имеем два отношения, схемы которых приведены ниже. Первичные ключи на схемах подчеркнуты.

Первое отношение имеет схему R={ № лифта, Индивидуальный номер слесаря, № дома, Дата последнего обслуживания}.

Соотношение ключей и детерминантов в нем приведено ниже:

Таблица 56

Детерминанты	Ключи
№ лифта	№ лифта

Второе отношение имеет схему R={ Индивидуальный номер слесаря, Имя слесаря}.

Множества детерминант и ключей в нем эквивалентны.

Таблица 57

Детерминанты	Ключи
Индивидуальный номер слесаря	Индивидуальный номер слесаря

Первое отношение содержит внешний ключ Индивидуальный номер слесаря, оно является ссылающимся, в то время как второе отношение – ссылочным.

Дано множество функциональных зависимостей F={A®BC; B®E; C®B; C®D; D®A}, атрибуты, входящие в них, полностью формируют схему отношения.

Задача. Привести отношение в НФБК, если оно в ней не находится.

Решение:

Предварительный анализ множества функциональных зависимостей показывает на то, что в нем присутствуют эквивалентные атрибуты, поэтому получению неизбыточного покрытия должен предшествовать этап выявления эквивалентных атрибутов.

С этой целью построим замыкания для левых частей функциональных зависимостей (см. Таблица 58).

Таблица 58

№	Вывод	Основание		№	Вывод	Основание
1.	A®A	β1		1.	B®B	β1
2.	A®BC	дано		2.	B®E	дано
3.	A®ABC	Β2		3.	B®BE	β2
4.	C®D	дано
5.	A®ABCD	β2
	A+=R				B+={BE}

№	Вывод	Основание		№	Вывод	Основание
1.	D®D	β1		1.	C®C	β1
2.	D®A	дано		2.	C®B	дано
3.	D®AD	β2		3.	C®BC	β2
4.	A®BC	дано		4.	C®D	дано
5.	D®ABCD	β2		5.	C®BCD	β2
				6.	D®A	дано
				7.	C®ABCD	β2
	D^+=R			8.	C^+=R

Далее сопоставим множества детерминант и ключей. Очевидно, что не все детерминанты в этом отношении являются ключами (см. Таблица 59), следовательно, отношение не находится в НФБК и подлежит декомпозиции. Поскольку в отношении присутствуют несколько эквивалентных атрибутов, то очевидно, что декомпозицию целесообразно осуществлять на кольцевом покрытии, которое имеет вид: G={(A, C, D) ®B; (B) ®E}.

Таблица 59

Детерминанты	Ключи
A	A
B	C
C	D
D

После выделения каждой СF-зависимости в отдельное отношение имеем:

R(r₁)={ABCD} и R(r₂)={BE}.

Таблица 60

Соотношение детерминант и ключей для отношения r1		Соотношение детерминант и ключей для отношения r2
Детерминанты	Ключи		Детерминанты	Ключи
A	A		B	B
C	C
D	D

Как очевидно из приведенной выше таблицы (см. Таблица 60), вновь полученные отношения будут находиться в НФБК.

Даны схемы трех отношений:

R(Лифт)={ № лифта, № дома, Индивидуальный номер лифтера};

R(Дом)={ № дома, Количество этажей, Количество подъездов};

R(Лифтер)={ Индивидуальный номер лифтера, Имя лифтера, Разряд}.

Задача. Вывести № домов, которые обслуживают лифтеры первого разряда и количество этажей в них.

Решение:

Анализ схем отношений показывает, что реализация запроса требует соединения всех трех отношений. Однако целесообразно перед соединением кортежей уменьшить мощность соединяемых отношений. С этой целью следует вначале осуществить операцию выбора на отношении Лифтер и только затем выполнить соединения вновь полученного отношения с остальными двумя. Список домов с указанием в них количества этажей выводится при осуществлении операции проекции.

1. Выделим всех лифтеров первого разряда:

r₁= s_{разряд=1}(Лифтёр).

Выполним соединение 2-х исходных отношений: Лифт и Дом по атрибуту № дома r₂ = Лифт [№ дома = № дома] Дом.

Схема вновь полученного отношения будет иметь вид:

R(r₂)={ № лифта, № дома, Индивидуальный номер лифтера, Количество этажей, Количество подъездов}.

Теперь выполним соединение вновь полученного отношения r₂ c отношением r₁ по атрибуту Индивидуальный номер лифтёра.

r₃ = r₂ [Индивидуальный номер лифтёра = Индивидуальный номер лифтёра ] r₁

В результате получим отношение со схемой:

R(r₃)={ № лифта, № дома, Индивидуальный номер лифтера, Количество этажей, Количество подъездов, Имя лифтера, Разряд}.

2. Выполним операцию проекции во вновь полученном отношении на атрибуты: № дома и Количество этажей:

r₄=p _{№ дома,Кол-во этажей} (r₄).

Итогом этой операции будет отношение со схемой R(r₃)={ № дома, Количество этажей}.

1. Дейт К. Введение в системы баз данных//7-издание. М.; CПб.: Издательский дом “Вильямс”, 2001. – 1012 с.

2. Диго С.М. Проектирование и использование баз данных. - М.: Финансы и статистика, 1995. - 208 с.

3. Джексон Г. Проектирование реляционных баз данных для использования с микро ЭВМ. - М.: Мир, 1991. - 252 с.

4. Коннолли Т. и др. Базы данных: проектирование, реализация, сопровождение. –М: Диалектика, 2000. – 1120 с.

5. Кузнецов С.Д. Введение в системы управления базами данных //СУБД. - 1995. - №1,2,3,4, 1996. - №1,2,3,4,5.

6. Мейер М. Теория реляционных баз данных. - М.: Мир, 1987. - 608 с.

7. Ульман Д. Базы данных на Паскале. - М.: Машиностроение, 1990. - 386 с.

8. Ульман Д., Уидом Д. Введение в основы баз данных.-М.: Издательство “Лори”, 2000 –376 c.

9. Чен П. Модель "сущность-связь" - шаг к единому представлению о данных //СУБД. - 1995. - №3. - С.137-158.

ОГЛАВЛЕНИЕ

1 РЕЛЯЦИОННАЯ МОДЕЛЬ ХРАНЕНИЯ ИНФОРМАЦИИ________________ 5

1.1 Основные понятия________________________________________________ 5

1.2 Идентификация объектов и их свойств (атрибутов)___________________ 6

1.3 Ключи___________________________________________________________ 8

1.3.1 Первичный ключ______________________________________________ 8

1.3.2 Внешние ключи______________________________________________ 11

1.3.3 Целостность базы данных______________________________________ 12

1.4 Функциональные зависимости_____________________________________ 13

1.4.1 Установление функциональных зависимостей_____________________ 13

1.4.2 Классификация функциональных зависимостей___________________ 14

1.5 Аксиомы вывода_________________________________________________ 15

1.5.1 Аксиомы Армстронга_________________________________________ 15

1.5.2 Независимость аксиом вывода__________________________________ 16

1.5.3 b - аксиомы_________________________________________________ 17

1.6 Выводы_________________________________________________________ 17

1.6.1 Выводы с использованием аксиом Армстронга____________________ 18

1.6.2 RAP последовательности вывода________________________________ 18

1.7 Замыкание атрибутов. Определение и обоснование ключей в отношении 19

1.8 Избыточные функциональные зависимости_________________________ 20

1.9 Эквивалентные множества функциональных зависимостей (покрытия) 20

1.9.1 Неизбыточное покрытие_______________________________________ 22

1.9.2 Минимальное покрытие_______________________________________ 23

1.9.3 Редуцированное покрытие_____________________________________ 23

1.9.4 Оптимальное покрытие_______________________________________ 24

1.9.5 Каноническое покрытие_______________________________________ 24

1.9.6 Комплексные функциональные зависимости______________________ 25

1.9.7 Кольцевое покрытие__________________________________________ 26

2 Нормальные формы___________________________________________ 27

2.1 Первая нормальная форма (1НФ)__________________________________ 27

2.2 Вторая нормальная форма (2НФ)__________________________________ 28

2.3 Третья нормальная форма (3НФ)__________________________________ 29

2.4 Нормальная форма Бойса - Кодда__________________________________ 30

2.5 Теорема Хеза. Частные случаи декомпозиции без потерь______________ 31

2.5.1 Декомпозиция на кольцевом покрытии___________________________ 35

3 РЕЛЯЦИОННАЯ АЛГЕБРА__________________________________________ 35

3.1 Операции над отношениями_______________________________________ 35

3.2 Элементарные операторы реляционной алгебры____________________ 36

3.2.1 Унарные операторы реляционной алгебры________________________ 37

3.2.2 Бинарные операторы реляционной алгебры_______________________ 39

4 ЗАДАНИЯ ДЛЯ КОНТРОЛЬНЫХ РАБОТ_____________________________ 41

4.1 Задание 1. Формализация предметной области______________________ 41

4.2 Задание 2. Формирование функциональных зависимостей____________ 47

4.3 Задание 3. Построение выводов____________________________________ 51

4.4 Задание 4. Вычисление покрытий__________________________________ 51

4.5 Задание 5. Определение ключей отношения_________________________ 52

4.6 Задание 6. Выявление аномалий, обусловленных избыточным дублированием _______________________________________________________ 53

4.7 Задание 7. Нормализация до НФБК________________________________ 53

4.8 Задание 8. Декомпозиция без потерь________________________________ 54

4.9 Задание 9. Нормализация до НФБК. Частные случаи________________ 57

4.10 Задание 10. Формирование запросов с использованием операторов реляционной алгебры______________________________________________________________ 58

5 ПРИМЕРЫ ВЫПОЛНЕНИЯ И ОФОРМЛЕНИЯ КОНТРОЛЬНОЙ РАБОТЫ 60

5.1 Пример выполнения задания № 1__________________________________ 60

5.2 Пример выполнения задания № 2__________________________________ 60

5.3 Пример выполнения задания № 3__________________________________ 60

5.4 Пример выполнения задания № 4_________________________________ 60

5.5 Пример выполнения задания № 5_________________________________ 60

5.6 Пример выполнения задания № 6__________________________________ 60

5.7 Пример выполнения задания № 7__________________________________ 60

5.8 Пример выполнения задания № 8__________________________________ 60

5.9 Пример выполнения задания № 9__________________________________ 60

5.10 Пример выполнения задания № 10_________________________________ 60

6 библиографический список__________________________________ 60

[1] Собственное подмножество это подмножество, которое принадлежит данному множеству, но не равно ему.

[2] Если в каком-то кортеже отсутствуют данные о значении атрибута, говорят, что этот атрибут допускает неопределенность(NULL). Признак NULL присваивается атрибуту, когда действительное значение не известно. NULL не эквивалентно ни нулевому значению, ни пустой строке, то есть это полная неопределенность.

[3] В рассматриваемом множестве неполной является первая функциональная зависимость, так как имеет место функциональная зависимость X®Z, в ее отсутствии первая функциональная зависимость является полной.

[4] На самом деле кольцевое покрытие – это всего лишь особая форма записи всех перечисленных выше покрытий, которая применяется для представления множеств функциональных зависимостей с эквивалентными левыми частями.

[5] В таблице выделены кортежи, которые появились после выполнения операции соединения над проекциями и не имели места в исходном отношении.

[6] В контрольной работе студент должен обосновать заключение о том, что данное множество атрибутов является ключом отношения. (см. 5.5)

Дата добавления: 2014-12-17