Многозначные зависимости.

Теорема для многозначной зависимости : многзначная зависимость существует , если при заданных значениях атрибутов , существует множество состоящее из нулей ( или более взаимных значений атрибутов y) , причем множество значений атрибутов y не связано со значениями атрибутов в отношении u-x-y . обозначение: xàày.

Аксиома 1) –дополнение для многозначной зависимости: если x прин u , y прин u , xàà y , то имеет место многозначная зависимость xààu-x-y

Аксиома 2)—пополнение для многозначной зависимости : если x прин u, v прин u , w прин u, y прин u, v прин w , x прин y , то имеет место многозначная зависимость

W объединено k àà v объединено y

Аксиома 3) – транзитивность для многозначной зависимости : если x прин u , y прин u , то имеет место многозначная зависимость xàày , yàà x , то имеет место xààz-y .

Т.о. формальная проверка многозначной зависимости должна выполняться на множестве z всех возможных экземпляров кортежей рассматриваемого отношения.

КЛЮЧИ ОТНОШЕНИЙ

Формальное определение ключа.

Если R-схема отношения с атрибутами: A1 An, и множество F функциональных зависимостей X-подмножество множества атрибутов, то X называют ключом в случае выполнения следующих условий:

1. зависимость X-> A1 An принадлежит полному замыканию (F+) (полному множеству функциональных зависимостей), которое можно получить из F с помощью правил вывода;

2. ни для какого собственного подмножества X зависимость Y из атрибутовY-> A1 An,Y принадлежит X , не принадлежит полному замыканию F+.

Условие (2) ставит вопрос о минимальности ключа. Данный ключ только тогда будет являться ключом отношений, когда он является минимальным (max ссылок связей в отношениях). В противном случае ключом будет 1 или более элементов из его подмножеств.

ОПР. (о первичных атрибутах).

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

Нормализация отношений (подразумевается неизбыточность базы)

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

1.выбрать для отношений первичные (и возможные) ключи, которые должны быть минимальными.

2.выбрать состав отношений базы, который должен быть минимальным (отличающийся минимальной избыточностью атрибутов).

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

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

5.разброс времени ответа (время реакции системы) на различные запросы к БД должны быть минимальным (доли секунд, мкс).

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

Пусть существуют реляционные БД со следующей схемой и экземпляром отношения: поставка (индекс, название поставщика, адрес, товар, цена).

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

1.Аномалия удаления

В данном примере возникнет при попытке удаления всех картежей, где существует поставка от одного поставщика. В этом случае в системе теряется адрес и название поставщика (хотя с ним может существовать договор и т.д).

2.Аномалия включения

Возникает в том случае, когда с поставщиком заключается договор, но поставок от поставщика не было, в данном случае нельзя включать в БД название поставщика и его адрес, так как нельзя полностью сформировать картеж (нет данных о поставщиках).

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

Введены 5 уровней схем нормализации отношений.

Поднимаются согласно правилам вложенности по возрастанию номеров.

СХЕМА.

Если находится в 4 НФ, то и находится в 3 УНФ, 3 НФ, 2 НФ, 1 НФ.

1 НФ.

Схема R находится в 1 НФ тогда и только тогда, когда все входящие в нее атрибуты являются атомарными.

2 НФ.

Если X-ключ отношения R, Y принадлежит X, А является непервичным атрибутом отношения R, то говорят что в отношении R имеет место частичная зависимость (неполная функциональная зависимость) X->A и Y->A. Схема отношения R находится во 2 НФ, если она находится в 1 НФ, и каждый ее непервичный атрибут функционально полно зависит от первичного ключа отношения, находящегося во 2 НФ.Может обладать аномалиями для операции включения, удаления и модификации БД.

3 НФ.

Схема R находится в 3 НФ, если не существует ключа X для R множества, атрибута Y принадлежит R и непервичного атрибута А из R таких, что выполняется следующее: X->Y, Y->A, Y-/>X (для R).

Схема R находится в 3 НФ, если она находится во 2 НФ, и каждый непервичный атрибут нетранзитивно (не напрямую) зависит от первичного ключа. В тех случаях, когда отношение имеет только 1 ключ и в нем отсутствуют многозначные зависимости, 3 НФ освобождается от избыточности и освобождается от аномалий включения, удаления и модификации БД. В тех случаях, когда в отношении отсутствует многозначные зависимости, но существует 2 и более возможных ключа. 3 НФ может иметь аномалии операций. В этом случае для снятия их рассматривается 3 УНФ (НФ Бойса-Кодда).

4 НФ.

Если в отношении R присутствуют многозначные зависимости, то схема отношения должна находится в 4 НФ. От 3 НФ отличается тем, что существует многозначная зависимость из X->->Y {0}, Y-подмножество X, но X содержит какой-либо ключ отношения R.

5 НФ (Проекционно-соединительная).

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

Если R={A1 An} P={R1 Rk}

Композиция R1 U R2 U U Rk={A1 An}

МЕТОДЫ ФИЗИЧЕСКОЙ ОРГАНИЗАЦИИ ДАННЫХ.

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