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

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

з

аписывалось бы так:

В случае, когда отн-е сост. из 1 корт., фигурные скобки иногда опускаются. Для корт. с ! атрибутом опускаются угловые скобки.

Утв. Пост-е отн-е с любым числом корт. k и любым числом атриб. n м.б. построено из пост-х отн-й с 1 корт. и 1 атрибутом с помощью операторов соединения и объединения.

Df: r(R); A, В – атр., AR, В не  R – A. Пусть R = (R – A) B, тогда r с A, переим-м в В (обозн. _АВ(r)), есть отн-е r(R ) = {t | tr, t (R – A) = t(R – A) & t (B) = t (A)}.

Зам. Треб-ся, чтобы А и В имели один домен.

Пусть r(R), A₁,…, A_k  R; B₁,…, B_k  R – (A₁…A_k­) (1); i: dom(B_i) = dom(A_i). Обозн. одноврем. переим-е атр-в A₁,…, A_k в B₁,…, B_k как _{A1,…, AkB1,…, Bk}(r). Оно не всегда м.б. запис. в виде посл-ти переим-й без введ. доп. атр-в, наприм. _{A, B  B, A} не удовл. условию (1) – различные имена атрибутов, но один домен.

20. Оп-и реляц. алгебры: эквисоед-е, естественное и -соед-е.

Df: r(R), s(S), RS =  (это не сильное огр-е, т.к. путем переим-я атр-в в s и r можно добиться  -я их схем), A_i R , B_i S , dom(A_i) = dom(B_i), i=1…n (A_i и B_i м.б. одинак.). Эквисоед-м r и s по A₁, A₂,…,A_m и B₁, B₂,…, B_m наз-ся отн-е q(RS) = {t | t_r r, t_ss, t(R) = t_r, t(S) = t_s, t(A_i) = t(B_i)}. Обозн. q(RS)=r[A₁=B₁, A₂=B₂,…, A_m = B_m] s.

Зам. Если в эквисоед-и нет сравнений, то r [ ] s = r  s.

Df: Пусть r(R) и s(S) – отношения. Соединением r и s называется отношение r  s = q(RS) = {t(RS)|  t_r  r, t_s  s : t_r = t(R), t_s = t(S)}.

Утв. Эквисоед-е м.б. выраж. через переимен-е и естеств. соед-е.

Обозн.  - мн-во символов бинарных оп-й над парами доменов.

Df: Если знак сравнения , а A и B – атр., то говорят, что A -сравним с B, если  – бинарное отношение в dom(A)  dom(B).

Df: Атр. A -сравним, если он -сравним сам с собой.

Расширим оп-р выбора, обозн-в _AB, . Если r(R), атр. A, BR, a  dom(B) – const, A и B -сравнимы, то _AB(r) = {t  r | t(A)a}.

Допускается и сравн-е между атрибутами: _AB = {t  r | t(A)t(B)}.

Df: r(R) и s(S) – отношения, для кот. RS = , и пусть A  R и B  R -сравнимы для . Тогда -соединением называется отношение q(RS) = {t | t_r r, t_ss, t(R) = t_r, t(S) = t_s, t_r(A)t_s(B)}, которое обозначается q(RS) = r [AB] s.

Эквисоединение – это расширенное соединение для сравнения разных столбцов на равенство. Можно не ограничиваться равенством, а воспользоваться любым .

21. Реляционной алгебра; теорема о полноте ограниченного множества операторов (без доказательства).

Реляционная алгебра над U, D, dom, R, d,  – семиместный кортеж B=( U, D, dom, R, d, , O), где O – множество операторов объединения, пересечения, разности, активного дополнения, проекции, естественного соединения, деления, переименования, которые используют атрибуты из U, и оператор выбора, использующий операторы из .

Здесь U – множество атрибутов (универсум), D – множество доменов, dom – полная функция из U в D, R = {R₁, R₂,…, R_p} – множество схем, R_i  U, d = {r₁(R₁), r₂(R₂),…, r_p(R_p)} – множество наборов отношений,  – множество бинарных отношений над доменами из D.

Теорема. Для выражения E над реляционной алгеброй существует выражение E’ над ней же, которое определяет ту же функцию и использует лишь операторы (1) постоянных отношений с единственным атрибутом и единственным кортежем, (2) выбора с одним сравнением, (3) естественного соединения, (4) проекции, (5) объединения, (6) разности, (7) переименования.

Следствие. Для реляционной алгебры с операцией дополнения в формулировке предыдущей теоремы изменится пункт (6): Для выражения E над реляционной алгеброй с операцией дополнения существует … (6) дополнения, (7) переименования.

22. Операторы расщепления и фактора.

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

Определение. Пусть (t) – предикат на кортежах над R, тогда расщеплением r по  называется пара отношений (s, s), каждое со схемой R, такие, что s = {tr | (t)} и s = { tr |(t)}. Обозначается эта пара SPLIT_ (r).

Определение. Пусть дано отношение r(R) и B₁, B₂,…, B_k  R, а L  R. FACTOR(r; B₁, B₂,…, B_k; L) = (s, s), где s = s((R – B₁B₂…B_k)L), s = s (B₁B₂…B_kL), причём по L возможно осуществить соединение s и s.

23. SQL: общая характеристика, основные понятия.

24. SQL: функции агрегирования. Примеры.

25. SQL: группировка, условия выборки. Примеры.

26. SQL: формат-е, упорядоч-е, связь с групп-кой. Примеры.

27. SQL: соед-е 2-х и > таблиц, виды соединений. Примеры.

28.

29.

30.

31.

32.

33.

34.

35. Методы хранения данных и доступа к ним. Физически последовательный, индексно-последовательный и индексно-произвольный доступ.

Определение. Эфф-ть доступа (ЭД) – число лог. обращ. / число физич.обращ. при выборке элемента данных.

Определение. Эфф-ть хранения (ЭХ) – число информационных байтов / число физ. при хранении.

Физ. посл-ый: Предпол. физ. располож. записей в лог-й посл-ти. Для выб. записи необх. просмотреть все пред. Несмотря на выс. ЭХ, из-за оч. низкой ЭД исп-е его огран. ЭХ = 1, ЭД низка, зависит от длины файла.

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

И-Пос: Инф-ый файл размещ-ся по блокам одинак. велич. Начало блока заполнено, а конец свободен. Индекс блока - его I-я или посл. запись. Индексы групп-ся в инд-ый файл, кот. упорядочен по первичному ключу. Поиск по индексу, затем по ссылке выб-ся I-я (или посл.) запись блока, в блоке поиск идет послед-но.

Добавл. записи идет в своб. место выбранного блока. Если своб. места нет, ее либо размещают в новый блок (область переполн-я), либо делят блок пополам, формируя 2 новых. ЭД зав. от размера базы, размера блоков и наличиия в них своб-х мест. ЭХ в зависит от объема свободного места в блоках и от величины индексов.

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

ЭД зависит от способа поиска записи в индексе. ЭХ зависит от размера индекса и ссылки.

36. Методы хранения данных и доступа к ним. Инвертированный, прямой и хешированный доступ.

Прямой: Взаимно 1-значное соотв-е между ключом и адресом записи. Некот. адресная ф-я форм-ет адрес, по кот. выб-ся запись. ЭД=1. ЭХ зав. от плотности размещ-я ключей. В общем случае метод довольно расточителен.

Инвертир-й: При инвертир-м методе проводится по зн-ю любого поля. Для каждого поля существенно его имя, знач-е и место в информ-ом файле. Инвертир-я табл. групп-ся по именам полей, кот. групп-ся по знач-м: строки с =-ми зн-ми размещ-ся в 1 группу. Поиск в табл. произв-ся каким-то способом (например, И-Пр), выбирается ссылка на запись. Метод обычно исп-ся лишь для поиска. Особенно эффективно применение инвертированных таблиц при выборке данных по совокупности критериев, если атрибуты имеют сравнительно небольшой диапазон значений. ЭД зав. от эфф-ти поиска в табл., но в любом случае она ниже 0,5 (доступ к таблице + доступ к базе). ЭХ зависит от метода хранения таблицы и от числа инвертируемых полей.

Хешированный: Метод представл. собой расшир-е метода ПД на случай отсутствия взаимно 1-значного соотв-я между ключом и адресом записи. Сущ. адресная ф-я (хеш-функция), кот. по ключу форм-ет адрес, но не исключ., что 1 и тот же адрес выделится разным ключам. Эта ситуация называется коллизией, а соотв-е ключи – синонимами. Алгоритм хеширования вкл. в себя механизм разрешения коллизий. ЭД зав. от 3-х факторов: от распр-я ключей, от кач-ва хеш-функции и от алг-ма разреш-я коллизий. ЭХ зав. от допустимого уровня ЭД. Чем свободнее таблица (файл), тем выше ЭД и ниже ЭХ.

37. Норм-е формы. Понятие о функц-й зав-ти. 1 норм-я форма. Полная функц-ая зависимость. 2 нормальная форма.

Df: Функциональная зависимость имеет место, если значение кортежа на одном множестве атрибутов единственным образом определяет их на другом. Другими словами, множество атрибутов Y функционально зависит от X тогда и только тогда, когда в любой момент времени для каждого из различных значений Y существует только одно из различных значений X.

Встречается и эквивалентный термин: множество X определяет Y. Обозначение – X  Y.

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

1НФ: Df: Отношение находится в 1НФ, если все его атрибуты атомарны.

Df: Атрибут, входящий в ключ, называется первичным.

Df:. Функц-я зав-ть X=(A₁,A₂,...,A_k)B полная, если B зависит от всех A_i из X. Если существует X'B, где X' – собственное подмножество X, функциональная зависимость неполная.

2НФ: Df: Отношение находится во 2НФ, если каждый непервичный атрибут функционально полно зависит от ключей.

38. Понятие о транзитивной зависимости. 3 нормальная форма и нормальная форма Бойса-Кодда.

Df: Атрибут A транзитивно зависит от X, если существует Y такой, что XY & (YX) & YA влечет XA.

Определение. Отношение находится в 3НФ, если в нем нет транзитивной зависимости атрибутов от первичных атрибутов.

Ex: реш-ся зад., связ-я с опред-ем складов для отдел-ий больницы. Зад. ставится руков-ом отд-я, для кот. важно, чтобы за его отд-м был закрепл. склад опред-го объема, причем только 1. Тогда для отн-я со схемой хранение(Отделение, Склад, Объем) сущ. ! функц-ая завис-ть: Отделение  Склад. Через некот. время выяснилось, что нужно следить и за складами вообще, что порождает II-ю функц-ю зав-ть: Cклад  Объем. Т.о., отн-е оказалось не в 3НФ (сущ. транзитивная зависимость объема от отделения через склад).

Аномалии: Включ-я: нет отдел-я, получ-го товар с этого склада – нет сведений об объеме. Удал-я: отдел-е перестает получать товар – нет данных о складе. Обновл-я: измен. объема склада - полный пересмотр. Преобразование: хранение(Отделение, Склад), объем_склада(Склад, Объем). Конец примера

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

39. Многозначная зависимость. 4 и 5 нормальные формы.

Определение. A многозначно определяет B в R (или B многозначно зависит от A), если каждому значению A соответствует множество (возможно, пустое) значений B, не зависимых от других атрибутов из R. Обозначение: AB.

Определение. Отношение находится в 4НФ, если в нем отсутствует нефункциональные многозначные зависимости. Другое определение – для любой нетривиальной зависимости XY множество атрибутов X содержит ключ).

Определение. Отношение находится в 5НФ, если любая зависимость по соединению определяется возможными ключами отношения.

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

Пример

R1(A, B, C) R2(A, B) R3(B, C) R4(A, C)

a1 b1 c1 a1 b1 b1 c1 a1 c1

a1 b1 c2 a2 b1 b1 c2 a1 c2

a2 b1 c1 a2 b2 b2 c1 a2 c1

a2 b1 c2 a3 b1 b2 c2 a2 c2

a3 b1 c1 a3 b2 a3 c1

a3 b1 c2 a3 c2

a3 b2 c1

a3 b2 c2

Отношение находится в 4НФ: нет многозначных зависимостей, но здесь есть явная избыточность. Следующее преобразование переводит его в 5НФ. Возможность восстановления очевидна.

40. Проектир-е данных. Модели. Роль польз-ля в проектир-ии.

Обычно для проектир-я данных исп-ся модель «Сущность-Связь» (ER-модель), которая граф-ки выр-ся ER-диаграм-ми. Сущ. разл. модиф-и представления (нотации) диаграмм, кот. поддерж-ся разл-ми средствами проектир-я прогр. систем (CASE-средствами), в частности, ERWin.

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

Процесс проектир-я: построение концептуальной модели (КМ), на основе кот. строится логическая (ЛМ). Чтобы определить КМ, необход. инф-я о предметной области (ПО). Ее получают на этапе анализа требований. Сложность этапа определяется необх-ю перевода неформальных представл-й заказчика в формальные спецификации. Рез-т вып-ния этого этапа – КМ, представл-я проектными требованиями. Реально ПТ редко можно назвать полноц. моделью, т.к. любая модель должна давать на каком-то уровне адекватное представл. о ПО. Получ-е же треб-я зачастую выступают как совок-ть представл-й о ней разных групп польз-лей. Поп. в наст. время направл. проектир-я – перепроект-е технолог-х процессов – отрицает такой подход т.к. он консервирует сущ-ю технологию и не дает выделить цель произв-ва. А раз невозм. выделить общую цель произв-ва, результат данного этапа исслед-ия нельзя считать моделью.

Реально все св-ва ПО представл. лишь КМ и след-е за ней. Как известно, КМ – наиб. общее представл. об инф-ном содержании ПО. Она единственна для проекта, обладает стабильностью по отношению к внешним и внутренним представлениям данных.

41. Этапы проектир-я. Концепт-е и логич-е проектирование.

КП: на этапе КП опред-ся информ-е потребности и лок. предст-я предм-ой области. Выявл-ся роль, назнач-е, взаимосвязь данных, проводится их глоб-я специф-я. Результат этапа – опис-е объектов данных и их взаимосв. без указания способа их физич. орган-ии.

2 стадии КП: анализ данных и орган-я их хран-я.

Анал. данных – сбор полной и точной инф-ии о данных ПО. Обычно исп-ся 1 из 2-х методов: анкетиров. и раб. с экспертами. В I-ом сл-е польз-лю предлаг-ся анкета, в кот. он должен дать свое предст-е о данных. Во II-м сл-е среди польз-ей выб-ся группа экспертов, кот. все и излагают.

II-я стадия сводится к разраб. графич-го представл-я получ-ой инф-ии в виде схемы, кот. вкл., в частности, исходные данные с формир-ми их проц-ми и результир. со ссылкой на использующие процессы. На этом же этапе уточ-ся степень важн-ти данных, выявл-ся и фикс-ся связи между ними. К данной работе, наряду с проектир-ком, полезно привл. админ-ра БД и представ-й польз-ля.

ЛП: Роль ЛП – отобр-е КМ в выбр-ю модель данных. На этом этапе необх. опред-ть отн-я и атрибуты, выделить ключи. На ряд атриб-в м.б. наложены огр-я, кот. выраж-ся в функц-х завис-ях между ними. Если выбрана реляц-я модель данных, в процессе проектирования след. так опр-ть отн-я, чтобы рез-те сформир-сь логич. схема БД, находящ-ся в 3 норм. форме. Эта схема не окончат-я, в процессе проектир-я она может корректир-ся, в рез-те чего нормализ-ть может нарушиться. В этом случае добавл-ся спец. этап нормал-и схемы.

42. Контроль достоверности данных, полномочия, ограничения целостности.

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

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

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

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

43. Строгое опред-е функциональной зависимости. Алгоритм проверки функциональных зависимостей.

Df: r(R); X,Y  R. Отн-е r удовл-ет функц-ной зав-ти XY, если _Y(_X=x(R)) имеет не более, чем 1 кортеж для каждого X-значения x. Другими словами, для t₁, t₂  r : (t₁(X)=t₂(X))(t₁(Y)=t₂(Y)).

X трив-но удовл-ет любым отн-м, Y удовл-т тем отн-ям, в кот. Y-знач-я всех корт-й совп-ют.

Алгоритм, проверяющий существование ФЗ XY (алгоритм SATISFIES). Суть его в том, что кортежи отн-я групп-ся по X-знач-ям, при этом все Y-знач-я для равных X-знач-й д.б. одинак.

Алгоритм SATISFIES:

Вход: отношение r, ФЗ XY.

Выход: истина, если r удовлетворяет XY, ложь в противном случае.

1) Отсортировать r по X-столбцам, группируя равные значения.

2) Если каждая группа X-кортежей имеет равные Y-значения, возвратить истину, в противном случае – ложь.

44. Аксиомы вывода.

Df: Будем говорить, что множество ФЗ F влечет ФЗ XY (F |= XY), если каждое отношение, удовлетворяющее всем зависимостям из F, удовлетворяет и XY.

Аксиома вывода – правило, устанавливающее, что если отношение удовлетворяет какой-то ФЗ, то оно удовлетворяет и некоторой другой ФЗ. Рассмотрим следующее множество аксиом.

F1. Рефлексивность: XX

F2. Пополнение (расширение левой части): (XY)  (XZY)

F3. Аддитивность: (XY, XZ)  (XYZ) позволяет объединить две ФЗ с одинаковыми левыми частями.

F4. Проективность: (XYZ)  (XY) В некоторой степени обратна F3.

F5. Транзитивность: (XY), (YZ)  (XZ)

F6. Псевдотранзитивность (XY), (YZW)  (XZW)

На самом деле эта система избыточна. Например, F6  F5 (для Z=), (F1, F2, F3, F5)  F6. Но она полна, то есть любая ФЗ, которая следует из F, может быть получена применением F1-F6.

Можно доказать, что {F1, F2, F6}– полное подмножество аксиом: (F1, F2, F6)  F3, (F1, F2, F6)  F4, F6  F5. Например, докажем F4. Пусть XYZ, тогда из (F1): YY и (F2): YZY. По (F6): XY. утверждение доказано.

Подмножество независимых аксиом {F1, F2, F6} носит название аксиом Армстронга.

45. А-мы Армстронга. Эквив-ть мн-в функц-х зав-тей.

Подмножество независимых аксиом {F1, F2, F6} носит название аксиом Армстронга.

F1. РефлексивностьXX

F2. Пополнение (расширение левой части) (XY)  (XZY)

F6. Псевдотранзитивность (XY), (YZW)  (XZW)

{F1, F2, F6}– полное подмножество аксиом: (F1, F2, F6)  F3, (F1, F2, F6)  F4, F6  F5. Например, докажем F4. Пусть XYZ, тогда из (F1): YY и (F2): YZY. По (F6): XY. утверждение доказано.

46. Вывод в системе аксиом функциональных зависимостей

Df. Послед-ть ФЗ P наз-ся послед-ю вывода на F, если каждая ФЗ из P либо принадл. F, либо след. из предыд. ФЗ в P после применения к ним одной из аксиом вывода.

Пример

F = {ABE, AGJ, BEI, EG, GIH}. Последовательность вывода определяется неоднозначно, например для ABGH она может выглядеть так:

1. ABE; 7. EG;

2. ABAB (F1); 8. ABG (F5);

3. ABB (F4); 9. ABGI (F3);

4. ABBE (F3); 10. GIH;

5. BEI; 11. ABH (F5);

6. ABI (F5); 12. ABGH (F3).

Эта последовательность является также последовательностью вывода для других ФЗ, например, ABGI.

Конец примера

Определение. Используемое множество в последовательности вывода P – множество ФЗ изF, принадлежащее P.

47. B-аксиомы вывода. Их полнота.

Эти три аксиомы называются B-аксиомами.

B1. Рефлексивность: XX

B2. Накопление: (XYZ,ZCW)(XYZC)

B3. Проективность: (XYZ)  (XY)

Пример

F = {ABE, AGJ, BEI, EG, GIH}. Приведём последовательность вывода для ABGH, использующую только B-аксиомы:

1. EIEI (B1); 6. EIGHI (B2); 11. BEI;

2. EG; 7. EIGH (B3); 12. ABABEI (B2);

3. EIEGI (B2); 8. ABAB (B1); 13. ABABEGI (B2);

4. EIGI (B3); 9. ABE; 14. ABABEGH (B2);

5. GIH; 10. ABABE (B2); 15. ABGH (B3).

Конец примера

Можно показать, что аксиомы Армстронга выводятся из B-аксиом. Из полноты системы аксиом Армстронга следует полнота системы B-аксиом.

48. RAP-последовательности вывода.

Df: Последовательность вывода XY из F, полученная при помощи B-аксиом называется RAP-последовательностью (по первым буквам названия B-аксиом), если она удовлетворяет следующим условиям:

1) первая ФЗ – это XX;

2) последняя ФЗ – это XY;

3) каждая ФЗ (за исключением первой и последней) либо принадлежит F, либо имеет вид XZ и получена с помощью аксиомы B2.

Пример

F = {ABE, AGJ, BEI, EG, GIH}. Выпишем RAP-последовательность вывода ABGH из F:

1. ABAB (B1); 6. EG;

2. ABE; 7. ABABEGI (B2);

3. ABABE (B2); 8. GIH;

4. BEI; 9. ABABEGH (B2);

5. ABABEI (B2); 10. ABGH.

Конец примера

Теорема. Пусть F – множество ФЗ. Если существует последовательность вывода из F для XY, то существует RAP-последовательность вывода из F для XY.

49. Ориентированный ациклический граф вывода

Ориентир. (directed) ациклич. (acyclic) граф (DA-граф) – это орграф, не имеющий циклов. Помеченный DA-граф – это DA-граф, каждой вершине кот-го поставлен в соотв-е некоторый элемент из множества меток L.

Df: DA-граф вывода над F (множеством ФЗ над R) – это DA-граф, помеченный символами атрибутов из R и построенный по следующим правилам.

1. Мн-во изолир-х вершин является DA-графом вывода над F.

2. Пусть DA-граф вывода над F содержит n вершин _i с метками A_i и в F сущ. ФЗ A₁A₂…A_kCZ (k  n). Опр-м новый граф, добавив к исх. DA-графу вывода вершину u с меткой C и дуги (₁, u), (₂, u),…, (_k, u). Полученный граф является DA-графом вывода над F.

3. Никакой другой граф не является DA-графом вывода над F.

Сокращённо DA-граф вывода над F называют DDA-графом над F.

Любой DDA-граф получ-ся 1-кратным применением правила (1) и многократным применением правила (2).

Df: H –DDA-граф, содерж. верш. , кот. не имеет вход. дуг. Тогда  наз-ся нач-ой верш. Нач-я верш. доб-ся с пом-ю прав (1).

Df: H –DDA-граф над F. H наз-ся DDA-графом для XY, если X – мн-во меток нач-х верш. и кажд. атриб. в Y – метка верш-ы в H.

Df: Используемым множеством в –DDA-графе H над F U(H) называется множество всех ФЗ в F, использованных при применении правила (2) во время построения графа H.

Th: Для мн-ва ФЗ F над R и ФЗ XY след. утверждения эквивалентны: «F |= XY;», «Существует последовательность вывода на F для XY;», «Существует DDA-граф над F для XY ».

50. Определение реляционной базы данных.

Ключ для схемы R – это подмножество K  R, такое, что любое отн-е r(R) удовлетворяет ФЗ XY, но никакое собственное подмножество K  K этим свойством не обладает.

Схема R некоторого отн-я сост. из 2-х частей: S и K, где S – мн-во атриб., K – мн-во выд-х ключей. Выделенным ключом может быть, в частности, суперключ. Введём обозначение R = (S, K).

Df. Схемой реляционной БД R над U (множеством атрибутов) называется совокупность схем отношений {R₁, R₂,…, R_n}, где R_i=(S_i, K_i), i = 1,2,…, n, ⁿ_i=1 S_i = U, и S_i S_j при i  j.

Df. Реляц-ой БД d со схемой БД R наз-ся такая совок-ть отн-ий {r₁, r₂,…, r_n}, r_i = r_i(S_i), что для каждой схемы R = (S, K) из R сущ. отн-е r в d со схемой S и удовлетворяющее каждому ключу из K.

Рейсы время

БД d={рейсы, время} имеет схему R = {(Пилот Рейс Дата, {Пилот Дата}), (Рейс Время, {Рейс})}.

51. Ряд следующих простых определений потребуются для дальнейшего изложения.

Df. Схема R = (S, K) вкл-ет ФЗ KR, если K – выдел-ый ключ из K.

Df. Схема БД R = {R₁, R₂,…, R_n} представляет множество ФЗ G = {KY | R_i  R, которое включает KY}. Говорят, что схема БД R полностью характеризует множество ФЗ F, если F  G.

Пример

Схема БД из пред. примера представл. Мн-во ФЗ G = {Пилот Дата  Рейс Дата, Рейс  Рейс Время}. Она полностью характеризует множество F = { Пилот Дата  Рейс Время, Рейс  Время}.

Df. ФЗ XY прим-ма к R, если XY – ФЗ над R, т.е. XR и YR.

Df. Пусть d={r₁, r₂, …, r_n} – база данных со схемой R = {R₁, R₂,…, R_n} над U. Она удовлетворяет F, если каждая XY из F⁺, применимая к схеме R_i из R, выполняется в отношении r_i.

Df. Пусть G – множество всех ФЗ в F⁺, которые применимы к некоторой схеме R_i в R. ФЗ в G⁺ называется навязанной R, а ФЗ из F⁺ – G⁺ – ненавязанной R. Множество F навязано схеме БД R, если каждая ФЗ в F⁺ навязана R.

Df. БД d со схемой R подчиняется множеству ФЗ F, если F навязано схеме R и d удовлетворяет F⁺.

Пример

Рассм. схему БД R = {R₁, R₂, R₃}, где R₁ = ABC, R₂ = BCD, R₃ = DE, и множество ФЗ F = {ABC, CA, AD, DE, AE}.

ФЗ AD и AE неприм-мы ни к одной схеме отн-я R. Мн-во F навязано схеме R, так как G = {ABC, CA, СD, DE} эквивалентно F. А множество {AD} не является навязанным R.

Конец примера