Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 2)

(GK)+=GK≠R

(EK)+=EGKL=R, X2=EK, i=2

3) i, как видим, возросло, значит опять 2)

2) E+=EG≠R, K+=K≠R

3) i не возросло, значит X=X2=EK - это ключ.

Теперь покажем, что схема не находится в 2НФ:

Найдем тройку X=EK - ключ, Y=E⊂X, H∉Y, H=G:

1) X→Y: EK→E

2) Y→H: E→G

3) Y↛X: E↛EK (K∉ E⁺)

Если разбить данную схему на две:

R1=(E, K, L)

Предположим тройку X=EK - ключ, Y=E⊂X, H∉Y, H=L:

1) X→Y: EK→E

2) Y→H: E↛ L (других непервичных атрибутов нет)

3) Y↛X: E↛EK (K∉ E⁺)

R2=(E, G) (нет троек), то они будут находиться во 2НФ.

БИЛЕТ 2

1. Определение функциональной зависимости в теории проектирования реляционных баз данных. Замыкание множества функциональных зависимостей. Аксиомы Армстронга.

Пусть R=(A1...An) является функциональной схемой отношения и X, Y - некоторые подмножества атрибутов этой схемы. Говорят, что X функционально определяет Y (X→Y), если в любом экземпляре отношения со схемой R не существует двух кортежей, совпадающих по подмножеству X и не совпадающих по подмножеству Y. Иначе говоря, если два кортежа совпадают по x, то они должны совпадать и по y

Например, R=(A1,A2,A3,A4), есть зависимости:

• A1→A2 (1)

• A1A3→A4 (2)

Предположим, что имеет место один экземпляр отношения со схемой R

Вторая ФЗ (2) имеет место быть, так как нет двух кортежей, совпадающих по этой паре. А первая ФЗ (1) не имеет место быть.

F – множество ФЗ на схеме R. Замыканием F (обозначается как F+) называется всё множество функциональной зависимости, которое логически следует из F (т.е. его можно вывести с помощью аксиом Армстронга).

• Рефлексивность: Если Y⊆X⊆R, то X→Y.-х всегда функционально определяет своё подмножество.

• Дополнение: если X→Y, Z⊆R, тогда XZ→YZ

• Транзитивность: Если X→Y, а Y→Z, то X→Z

1. Задача: 1. Проверить, находится ли схема отношений R в третьей нормальной форме, используя определение 3НФ. 2. Обладает ли схема отношений R следующими аномалиями: избыточностью, потенциальной противоречивостью, аномалией включения записей и аномалией удаления записей. Почему?

Исходные данные: схема отношений R= (номер магазина, адрес магазина, наименование товара, цена единицы товара)=(E, G, K, L) и множество функциональных зависимостей F=(EG, GE, EKL).

Найдем ключ:

1) i=0, X0=EGKL

2) (EKL)+=EGKL=R, X1=EKL, i=1

(GKL)+=EGKL=R, X1=GKL, i=1

(EGK)+=EGKL=R, X1=EGK, i=1

3) i, как видим, возросло, значит опять 2)

2) (EL)+=EGL≠R

(EG)+=EG≠R

(GL)+=EGL≠R

(LK)+=LK≠R

(GK)+=EGKL=R, X2=EK, i=2

(EK)+=EGKL=R, X2=EK, i=2

3) i, как видим, возросло, значит опять 2)

2) E+=EG≠R, K+=K≠R, G+=EG≠R

3) i не возросло, значит X=X2=EK и X=X2=GK - это ключи.

Теперь предполагаем тройку: X=EK, Y=E⊆R, H=L, L∉X

Проверяем три условия для неё:

1) X→Y, так как EK→E;

2) Y→H, E↛L

3) Y↛X, E↛EK, EK⊈E+

Таким образом, нет такой тройки, для которой выполняются все три условия (нет других непервичных атрибутов), а значит отношение находится в 3НФ.

Однако схема отношений R обладает следующими аномалиями:

• избыточностью – адрес магазина повторяется для каждого товара;

• потенциальной противоречивостью – при изменении адреса магазина необходимо изменить все записи, куда он входит;

• аномалией включения записей – если в магазине нет товаров, то нельзя включить информацию о нем;

• аномалией удаления записей – при удалении товара удаляется информация о магазине.

БИЛЕТ 3

1. Правила объединения, декомпозиции и псевдотранзитивности в теории реляционных баз данных (доказательство леммы).

Аксиомы Армстронга:

• Рефлексивность: если Y⊆X, то X→Y.

• Дополнение: если X→Y, Z⊆R, тогда XZ→YZ

• Транзитивность: если X→Y, а Y→Z, то X→Z

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

Правило объединения: если X→Y и X→Z, то X→YZ

1. X→XY (1 ФЗ и пополняем X);

2. XY→YZ (2 ФЗ и пополняем Y);

3. X→YZ (по аксиоме транзитивности).

Правило декомпозиции: если X→Y, а Z⊆Y, то X→Z

1. X→Y (по условию);

2. Y→Z (по аксиоме рефлексивности);

3. X→Z (по аксиоме транзитивности).

Правило псевдотранзитивности: если X→Y и WY→Z, то WX→Z

1. WX→WY (1 ФЗ и пополняем W);

2. WY→Z (по условию);

3. WX→Z (по аксиоме транзитивности).

1. Задача: вручную выполнить запрос методом хешированного соединения.

Исходные данные: 1) запрос: select R1.b, R2.c from R1, R2 where R1.a= R2.a; 2) таблицы: R1(a, b)= ((1, 3) (6, 7) (3, 8)), R2(a, c)= ((4, 6) (6,3) (11, 5)); хеш-функция: h(a)=a (mod 5).

БИЛЕТ 4

1. Алгоритм вычисления замыкания множества атрибутов в теории реляционных баз данных.

Пусть R - универсальная схема отношения, а X - некоторое подмножество атрибутов. Тогда замыканием множества атрибутов X+ называется совокупность атрибутов A_i1,A_i2...A_ik таких, что (X→A_i1,X→A_i2...X→A_ik).

Алгоритм построения является итерационной процедурой.

1. i=0. =X; ( - замыкание множества атрибутов на i-том шаге).

2. = ⋃V, где V - такое подмножество атрибутов в F, что Y→Z, Y⊆ , V⊆Z;

3. если = , то = , иначе i=i+1 и возвращаемся в пункт 2.

1. Задача: оценить число записей, возвращаемых запросом.

Исходные данные: 1) запрос: select * from R1, R2 where R1.b=3 and R2.c=5 and R1.a= R2.a; 2) число записей в таблицах: T(R1)= 1000, T(R2)= 500, мощности атрибутов: I(R1,b) =10, I(R2,c)=5, I(R1,a) =20, I(R2,a)=25.

БИЛЕТ 5 (док-во часть2 ?)

1. Алгоритм построения условно неизбыточного покрытия (УНП) для множества функциональных зависимостей F. Доказательство, что УНП является покрытием F.

Пусть F и G - два множества ФЗ. G называется покрытием F, если имеет место равенство G⁺=F⁺

Алгоритм построения УНП:

1) если в множестве ФЗ F встречаются ФЗ с одинаковой левой частью X, то следует объединить эти ФЗ в одну ФЗ и обозначим G (по аксиоме объединения).

2) для каждой ФЗ из G заменить её на X→ −X.

В конце получаем замыкание G⁺=F⁺

Доказательство:

1) Докажем, что если ФЗ X→Y∈F, то эта ФЗ принадлежит G+:

Из X→Y∈F следует (по определению), что Y⊆ и по (а1) получим: .

В алгоритме построения УНП в пункте 2 каждую ФЗ из G заменили на X→ −X. Далее дополним эту ФЗ используя (а2): X→( −X)⋃X= .

Из и X→ по (а3) получим: X →Y.

Значит, X→Y∈G⁺, по третьей аксиоме Армстронга.

2) Докажем, что если ФЗ X→Y∈G, то эта ФЗ принадлежит F+:

Y=X+−X

X→X+ (по определению)

X+→X+−X (1 аксиома Армстронга)

X+→X+−X=Y (3 аксимома Армстронга)

X→Y∈F+

1. Задача: как в алгоритме поиска физического плана с минимальной стоимостью меняются аргументы P-Q_j и Q_j в процедуре JoinPlan(P-Q_j, Q_j).

Исходные данные: логический план выполнения запроса, где соединяются 4-е подзапроса Q₁, Q₂, Q₃, Q₄.

БИЛЕТ 6

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

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

Пусть ρ=(R₁...R_n) - схема БД. Она будет обладать свойством соединения без потерь, если для любого экземпляра отношения r из R справедливо равенство:

, где - это проекция экземпляра отношения r на множество атрибутов

Алгоритм проверки схемы БД на свойство соединения без потерь:

ρ=(R₁...R_n)

R=(A₁...An)

1) построить таблицу T:

И заполнить таблицу T по правилу: если Aj∈Ri, то Tij=a, иначе Tij=bi

2) циклически просматривать ФЗ из F в любом порядке, и для очередной ФЗ X→Y∈F выполнить следующие действия:

• найти в таблице все строки, совпадающие по атрибутам X (по левой части);

• если хотя бы в одной такой строке значение атрибута Am∈Y=a, то во всех найденных строках присвоить Am=a;

• выполнить предыдущие два пункта для всех атрибутов Al∈Y;

• циклически выполнять предыдущие три пункта для всех ФЗ из F.

3) алгоритм останавливается, если при очередном просмотре всех ФЗ из F:

• не произошло никаких изменений в таблице T;

• какая-нибудь строка в T не стала состоять сплошь из символов a (наличие такой строки и говорит о выполнении свойства соединения без потерь).

1. Задача: построить схему базы данных, используя алгоритм синтеза «хорошей» схемы базы данных.

Исходные данные: универсальная схема отношений U=(A,B,C), исходное множество функциональных зависимостей пусто, т. е. F=.

БИЛЕТ 7

1. Доказать теорему:

Пусть ρ = (R₁, R₂) – схема базы данных, F – множество функциональных зависимостей на универсальной схеме отношения R. Тогда ρ обладает свойством соединения без потерь тогда и только тогда, когда справедлива хотя бы одна из следующих функциональных зависимостей:

1) R₁∩R₂ –> R₁ – R₂ ;

Характеристики

Список файлов ответов (шпаргалок)