Экзаменационный билет № 11

Корректная схема БД. Третья нормальная форма. Нормальная форма Бойса – Кодда.

• В некоторых случаях третью нормальную форму можно «улучшить» приведением в нормальную форму Бойса-Кодда

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

• Отношение находится в нормальной форме Бойса – Кодда, если оно находится в третьей нормальной форме и каждый детерминант отношения является ключом отношения

Экзаменационный билет № 12

Реляционная алгебра. Операции объединения, фильтрации и проекции.

• База данных - Набор таблиц

• Отношение ≈ Таблица

• Атрибут отношения - Столбец таблицы

• Кортеж отношения - Строка таблицы

• Степень (-арность) отношения - Количество столбцов таблицы

• Мощность отношения - Количество строк таблицы

• Домены и типы данных - Типы данных в ячейках таблицы

• Средства манипулирования отношениями базируются на традиционных теоретико-множественных операциях + специальные реляционные операции

• Существует несколько равносильных подходов к определению реляционной алгебры

• Теоретико-множественных операции:

  • объединения отношений

  • пересечения отношений

  • взятия разности отношений

  • расширенное декартово произведения отношений

• Введем следующие обозначения:

  • Ri – отношение i. Ri ={ri}

  • ri – кортежи отношения i

  • Ri = (атрибут 1, атрибут 2, … , атрибут N) – схема отношения i

• Первые три операции являются бинарными (в операции участвуют два отношения – операнда). Кроме того, эти операции могут производиться только над отношениями с  эквивалентными схемами

• Объединение двух отношений дает новое отношение, которое содержит кортежи принадлежащие либо к первому, либо ко второму отношению

• R = R1 È R2 = {r | r Î R1 Ú r Î R2}

• Кортежи - дубликаты в новом отношении отсутствуют

• Пересечением отношений называется отношение, которое содержит множество кортежей, принадлежащих одновременно к первому и второму отношениям

• R = R1 Ç R2 = {r | r Î R1  Ù r Î R2}

• Разностью отношений R1 и R2 называется отношение, содержащее кортежи, принадлежащие отношению R1 и не принадлежащие отношению R2

• R = R1 \ R2 = {r | r Î R1  Ù r Ï R2}

Экзаменационный билет № 13

Реляционная алгебра. Операции пересечения, расширенного декартового произведения.

• Расширенным декартовым произведением отношения R1 со схемой R1 = {A1, A2 , A3 , … , An} и отношения R2 со схемой R2 = {B1 , B2 , B3 , … , Bm} называется отношение R степени n+m со схемой R = R1 Ä R2 = {A1 , A2 , A3 , … , An, B1, B2, B3, …, Bm}, содержащее кортежи, полученные сцеплением каждого кортежа отношения R1 с каждым кортежем отношения R2

• Результатом операции фильтрации, заданной на отношении R в виде булевского выражения a, определенного на атрибутах отношения R, называется отношение R[a], включающее те кортежи из исходного отношения, для которых истинно условие выбора

• R[a(r)] = {r | r Î R Ù a ( r ) = “True”}

• Условие a может быть сколь угодно сложным, состоящим из термов сравнения с помощью связок И, ИЛИ, НЕ (Ù, Ú, Ø) и скобок

• В качестве термов могут выступать два атрибута, либо атрибут и константа из домена атрибута

• Проекцией отношения R на набор атрибутов B (R[B]) называется новое отношение со схемой, соответствующей набору атрибутов B, содержащему кортежи, получаемые из кортежей исходного отношения путем удаления из них значений, не принадлежащих атрибутам из набора B

• R[B] = {r[B]}

• Иногда эту операцию называют операцией горизонтального выбора

• В «табличных» терминах происходит отбрасывание выбранных столбцов таблицы

• Соединением отношений R и Q при условии b будет подмножество декартова произведения отношений R и Q, кортежи которого удовлетворяют b как выполнению условий

• R[ b ] Q = {(r, q) | (r, q) | r Ac qi q Bc = “True” i = 1, 2, … , k}

• где:

• SR = (A1 , A2 , A3 , … , An) и SQ = (B1 , B2 , B3 , … , Bm)

• Ac Ê {Ai } i=1,2,3,…n    Bc Ê {Bj } j=1,2,3,…n – сравнимые атрибуты

• qi - i-й предикат сравнения, определяемый из множества допустимых на домене операций сравнения

• Пусть даны два отношения R и T соответственно со схемами:

• SR = (A1 , A2 , A3 , … , An)

• ST = (B1 , B2 , B3 , … , Bm)

• A и B – наборы атрибутов этих отношений одинакового размера. Проекции R[A] и T[B] совместимы по объединению, то есть имеют эквивалентные схемы.

• Операция деления ставит в соответствие отношениям R и T отношение Q = R[A : B] T, кортежи которого являются теми элементами проекции R[A1], для которых T[B] входит в построенные для них множество образов

• Q = R[A : B] T = {r | r Î R [A1 ] Ù T[B] Í {y | y Î R [A] Ù (r, y) Î R}}