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