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

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

2) R₁∩R₂ –> R₂ – R₁.

1) Докажем, что при выполнении указанных условий схема БД обладает свойством соединения без потерь:

Получили строку, сплошь состоящую из a.

2) Теперь докажем обратное, что если ρ обладает соединением без потерь, то имеет место одна из ФЗ: (1) или (2).

r=ΠR1(r)⋈ΠR2(r) (3)

r – это R1⋃R2 (экземпляр универсальной схемы отношений)

Возможны два варианта:

1) Если bi≠bj, i≠j, то выполняется равенство (3);

2) Если некоторые bi совпадают, b1=b2, тогда для выполнения равенства (3) необходимо, чтобы выполнялось одно из двух:

• a1=a2;

• c1=c2.

2 и 3 кортежи - лишние. Чтобы они не были лишними, они должны совпадать с одним из других кортежей, чтобы их можно было вычеркнуть.

Предположим, a1=a2, тогда сработает ФЗ R1∩R2 –> R1 – R2.

Предположим, c1=c2, тогда сработает ФЗ R1∩R2 –> R2 – R1.

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

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

БИЛЕТ 8

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

Пусть дана схема БД ρ= (R1...Rn) и F - множество ФЗ.

(проекция F на множество Ri) - такое множество ФЗ X→Y, принадлежащее F+, что XY⊆Ri.

Схема ρ обладает свойство сохранения ФЗ, если:

Свойство обеспечивает декомпозицию ФЗ по схеме отношения (тогда проверку надо будет выполнять только в рамках отдельных таблиц при включении новой записи).

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

ρ=(R1...Rn)

1. построить условно-неизбыточное покрытие (УНП), взять H=∅;

2. каждую ФЗ из УНП разбить на ФЗ с одним атрибутом в правой части, то есть заменить (X → A1...Ak) на (X→A1, ..., X→Ak). Обозначить полученную ФЗ как G;

3. выбрать очередную ФЗ из G. Найти такую схему отношения Ri, для которой справедливо включение XA⊆Ri. Если такой схемы отношений не существует, то поместить ФЗ X→A в множество H;

4. если все ФЗ из G рассмотрены, то перейти к следующему пункту, иначе к предыдущему;

5. если H пусто, то завершить алгоритм. ρ обладает свойством сохранения ФЗ. Иначе перейти к следующему пункту;

6. просмотреть все ФЗ из H. Если какая-либо ФЗ X→A∈H не выводится из множества G−H, то завершить алгоритм. ρ не обладает свойством сохранения ФЗ. Иначе завершить алгоритм, и тогда ρ обладает свойством сохранения ФЗ.

1. Задача: написать оператор SELECT, соответствующий запросу; преобразовать этот оператор в формулу реляционной алгебры; оптимизировать эту формулу, используя законы реляционной алгебры; построить логический план выполнения оператора в графическом виде.

Исходные данные: 1) схема базы данных = (S, P, J. SPJ), схемы отношений S (Поставщик деталей) = (ном_пост, имя, состояние, город), P (Деталь) = (ном_дет, назв, цвет, вес, город), J (Изделие) = (ном_изд, назв, город), SPJ (Сборка) = (ном_пост, ном_дет, ном_изд, количество), 2) запрос: найти номера поставщиков, поставляющих белые детали.

БИЛЕТ 9

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

Пусть R=(A1...An) - некоторая схема отношения, а F - множество ФЗ.

Тогда X⊆R называется ключом схемы, если выполняются:

• X→A₁...A_n∈F⁺

• ∀Z⊂X, Z→A₁...An∉F⁺

X содержит минимальное число атрибутов, для которых выполняется предыдущее свойство (a).

Алгоритм построения ключа:

Базируется на определении ключа. Позволяет построить только один ключ.

1) i=0, X₀=A1...An

2) цикл по атрибутам A_j в X_i. Если =R, то X_i+1=X_i−A_j, i=i+1 и выйти из цикла; иначе продолжить цикл

3) если i возросло, то перейти к шагу (2);

иначе X= X_i - это найденный ключ.

Если атрибут Ai∈R входит в какой-либо ключ схемы отношения R, то он называется первичным. А если не входит ни в один, то называется непервичным.

Доказательство, что значение ключа всегда уникально.

Методом от противного.

Пусть у нас 2 одинаковых значений атрибута ключа X=X₁=X₂=x.

По определению ключа X→A₁...A_n∈F⁺. А при равных X у нас равны A₁...A_n.

Т.е. в схеме отношения у нас:

По определению в схеме отношений не может быть 2-х одинаковых картежей, т.е. предположение не выполнимо.

1. Задача: написать оператор SELECT, соответствующий запросу; преобразовать этот оператор в формулу реляционной алгебры; оптимизировать эту формулу, используя законы реляционной алгебры; построить логический план выполнения оператора в графическом виде.

Исходные данные: 1) схема базы данных = (S, P, J. SPJ), схемы отношений S (Поставщик деталей) = (ном_пост, имя, состояние, город), P (Деталь) = (ном_дет, назв, цвет, вес, город), J (Изделие) = (ном_изд, назв, город), SPJ (Сборка) = (ном_пост, ном_дет, ном_изд, количество), 2) запрос: найти имена поставщиков, поставляющих детали для изделия с номером ‘J1’.

БИЛЕТ 10

1. Аномалии схемы отношений. Определение третьей нормальной формы (3НФ).

Пусть A=(идентификатор поставщика, адрес, товар, цена) и есть одна схема ρ=R1=A

Данная схема БД обладает следующими недостатками (аномалиями):

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

• потенциальная противоречивость. Если у поставщика меняется адрес, то его необходимо изменить во всех кортежах, в которые он входит;

• аномалия включения кортежа. В выбранном отношении R пара атрибутов идентификатор-товар является ключом. При включении новой записи, атрибуты ключа не должны быть пустыми, поэтому в БД нельзя включить поставщика, если он в данный момент не поставляет товар;

• аномалия удаления. При удалении всех товаров, поставляемых поставщиком, теряется информация о самом поставщике.

Первопричиной этих недостатков является то, что R1 не находится в 3НФ.

Отношение находится в 3НФ, если не существует тройки X,Y,H (ключа X, подмножества атрибутов Y⊆R, не первичного атрибута H∉Y) для которой выполняются условия:

• X→Y∈F⁺;

• Y→H∈F⁺;

• Y→X∉F⁺.

1. Задача: представить оператор обновления в виде формулы реляционной алгебры.

Исходные данные: 1) отношение (таблица) r со схемой R(изделие) = (номер_изделия, название_изделия, город_изготовления)= (A, B, C); 2) оператор обновления (UPDATE) – заменить в таблице r название изделия «Р1» на название «Разъём1».

БИЛЕТ 11

1. Условия, когда схема отношений, находящаяся в третьей нормальной форме, имеет аномалии. Пример. Нормальная форма Бойса-Кодда.

Условия, когда схема в 3НФ обладаем аномалиями:

• схема отношения имеет 2 или больше ключей,

  • и любые 2 из них являются составными,

    • причём они имеют общий атрибут.

Пример:

R=(A,B,C,D) и F=(A→B,B→A,AC→D)

Два ключа: AC и BC

(AC)+=ACBD, (BC)+=BCAD

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

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