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}
МЕТОДЫ ФИЗИЧЕСКОЙ ОРГАНИЗАЦИИ ДАННЫХ.
Физичиские структуры данных показывают каким образом данные отражаются в среде хранения. При отражении данных с определенной логической структурой, с одной стороны должна сохранятся их симантика, а с другой должна обеспечиваться эффективность обработки данных. На физические структуры оказывает влияние АБД и запоминает устройства, так как размещение данных на разных носителях имеют свою специфику. По способу закрепления места в памяти различают позиционные и непозиционные структуры. В позиционных структурах место и роль элементов заранее однозначно определено, элемент имеет степень закрепления. Иногда структура БД становится гибкой, когда в ключ вводится логика, такие структуры становятся вычисляемыми или рандомизированными. В непозиционных структурах элементы жестко не закреплены, задается логический порядок следования данных, способ отображения связей между ними в памяти, а также порядок, согласно которому определяется следующий элемент. По способу отображения связей между элементами различают последовательно-смежные, списковые структуры.
В последовательных структурах элементы логически следуют друг за другом, располагаясь в смежных участках памяти. В списковых - связи между элементами данных передаются посредством адресных указателей. Для отражения связей между элементами данных используются символические указатели.
Символическая связь – повторение значения поля, по которому производится связывание. Обычно связывающий компонент – идентификатор данных. Связи между элементами данных отражаются с помощью битовых структур. В этом случае кроме файла, содержащего сведения об объектах создаются 1 или несколько битовых структур (битовых векторов или матриц), показывающих взаимоотношения элементов основного файла. Совокупность индекса и индексного массива является индексной структурой. В БД обычно используют довольно сложные многоуровневые логические структуры данных. Сокращение объема памяти в БД занимаются специализированные архиваторы, являющиеся утилитами БД. Проектирование физических и логических структур данных тесно связано между собой.
Последовательная организация хранения данных (ПОХД).
ПОХД обладает следующими преимуществами:
1.отсутствие дополнительной адресной информации и плотное размещение данных в запоминающей среде, приводящее к сокращению объема памяти.
2.возможность использования любых носителей информации.
3.сокращение времени обработки при условии, что порядок размещение на носителе совпадает с требованием в порядке обработки.
4.простота организации данных и манипулирование ими, так как идет увеличение объема памяти и уменьшение цены, то значимость 1 и 2 фактора снижается.
Последовательные структуры данных имеют недостатки:
1.неудобство корректировки.
2.необходимость разворачивания нелинейных логических структур в линейные.
3.трудности в обеспечении адекватного, интегрированного отображения предметной области.
4.длительность выборочного поиска.
5.адаптация новых элементов данных последовательную структуру должно выполняться согласно логическому порядку следующего элемента, что вызывает необходимость физического перемещения данных.
В последнее время в связи с широким распространением реляционной БД, использование последовательных данных в файлах увеличивается. Многие реляционные СУБД предусматривают организацию хранения каждого отношения данных в качестве видимого файла.
Списковая организация хранения данных.
Заключается в использование адресных указателей для связей элементов данных. Различают списковую организацию с совместным и раздельным хранением, с объектной, собственной, ассоциативной, адресной информацией, однонаправленные и двунаправленные списки. Такая классификация списковых структур традиционная. Взависимости от характера связывания элементов, списковая структура может связывать однотипные элементы данных в единую структуру – однородный список. На одном и том же множестве элементов может быть задано несколько связей, каждая из которых выделяет подмножество элементов, это списки – многосвязные. Если информация в списках одного типа, то информация называется гомогенной. Если информация разнородна, то список называется гетерогенным.
СХЕМА.
Многосвязные списки широко распространены, так как отображение в БД предметной области требует много связей. C другими такие структуры просты в реализации, позволяющие сократить дублирование данных, уменьшить время обработки данных за счет выделения подмножеств для различных запросов и сокращении в следствии этого числа просматриваемых элементов. Кроме связывания однотипных используются в БД разнородные (гетерогенные) структуры, соединяющие разнотипные элементы данных.