Понятие данных

• Название: Понятие данных
• Дата: 21.01.2021
• Размер: 1.56 Mb.
• Имя файла: BD-Bilety-2016.pdf
• Тип: Документы; #170274
• страница: 6 из 9

1. Рефлексивность
Если имеется некоторая совокупность атрибутов X = YZ (т.е. Y есть некоторое подмножество из X), тогда X  Y.
Тривиальная функциональная зависимость, в которой зависимость (правая часть) содержится в детерминанте
(левой части). Следствие (если Z = ∅): X  X
2. Пополнение (или расширение левой части)
Если существует функциональная зависимость X  Y, то XZ  YZ. Функциональная зависимость X  Y или принадлежит F, или может быть логически выведена из F с помощью описываемых правил
3. Транзитивность
Если X  Y и Y  W, то X  W
4. Псевдотранзитивность
Если X  Y и YZ  W, то XZ  W
Дано: X  Y, YZ  W.
Требуется получить XZ  W.
В соответствии с правилом 2, из X  Y следует XZ  YZ.
В соответствии с правилом 3, из XZ  YZ (вывели) и YZ  W (дано) следует XZ  W.
Из правила псевдотранзитивности, при Z = ∅ получим правило транзитивности

5. Аддитивность
Если X  Y и X  Z, то X  YZ
Дано: X  Y и X  Z
Требуется получить X  YZ
В соответствии с правилом 2, из X  Z можно получить XY  ZY (или YX  YZ)
В соответствии с правилом 4, так как X  Y (по условию) и YX  YZ (выведено), имеем XX  YZ (или X  YZ)
6. Декомпозиция
Если X  YZ, то X  Y и X  Z
Дано: X  YZ
Требуется получить X  Y и X  Z
В соответствии с правилом 1 YZ  Y и YZ  Z
В соответствии с правилом 3, из X  YZ и YZ  Y следует X  Y
Аналогично, из X  YZ и YZ  Z следует X  Z
7. Композиция
Если X  Y и Z  W, то XZ  YW
Дано: X  Y и Z  W
Требуется получить XZ  YW
В соответствии с правилом 2, из X  Y следует XZ  YZ, а из Z  W следует
ZY  WY (или YZ  YW)
В соответствии с правилом 3, из XZ  YZ и
YZ  YW следует XZ  YW

21. Понятие декомпозиции отношения. Декомпозиция с соединением без потерь. Декомпозиция с сохранением функциональных зависимостей.
Декомпозиция – разбиение универсального отношения на совокупность отношений, удовлетворяющих требованиям нормальных форм.
Декомпозицией схемы отношений называется замена ее совокупностью подмножества
R
, таких, что
Общий алгоритм:
1. Построим таблицу с n столбцами и k строками, где столбец j соответствует атрибуту А
j
, а строка i - схеме отношения
R
i
. На пересечении строки i и столбца j поместим символ aj, если атрибут A
j принадлежит R
i
. В противном случае поместим символ b ij
2. Многократно просматриваем каждую ФЗ из F, до тех пор, пока внесение изменений в таблицу станет невозможным. Просматривая зависимость ищем строки, которые совпадают по всем столбцам, соответствующим атрибутам из Х. При обнаружении таких строк отождествляем их символы в столбцах, соответствующих атрибутам из Y, по правилу a j
в a j
, b ij в b ij
3. Если после модификации строк таблицы оказывается, что некоторая строка равна a
1
, a
2
, ..., a k
, то декомпозиция d обладает свойством соединения без потерь. В противном случае декомпозиция d таким свойством не обладает.
Обозначения:
R(A
1
A
2
…A
n
) – схема отношения
U = {A
1
, A
2
, …A
n
} – универсальное множество атрибутов
X ⊆ U, Y ⊆ U, Z ⊆ U, W ⊆ U – некоторые подмножества атрибутов из U
XY – объединение атрибутов: X ∪ Y ≡ XY
Декомпозиция
Если X  YZ, то X  Y и X  Z
Декомпозицией схемы отношения R(A
1
, A
2
, …, A
n
) называется замена ее совокупностью подмножеств {R
i
} (подсхем) схемы
R таких, что R
1
∪ R
2
∪ … ∪ R
k
= R. Не обязательно, чтобы R
i
∩ R
k
= ∅ при i ≠ k
Декомпозиция с соединением без потерь
Теория реляционных баз данных говорит, что результаты запроса будут совпадать, если декомпозиция выполнена способом, при котором соединение R1 и R2 дает в точности исходное соотношение R – это декомпозиция без потерь.
Сохранение функциональных зависимостей
Проекцией
множества
функциональных
зависимостей
F на множество атрибутов
Z
(π
Z
(F)) называется множество зависимостей X  Y в F
+
, таких, что XY ⊆ Z
Говорят, что декомпозиция сохраняет множество функциональных зависимостей F, если из объединения всех зависимостей, принадлежащих π
Ri
(F), для i = 1, 2, …, k, логически следуют все зависимости, принадлежащие F

22. Проектирование БД с использованием теории нормализации. 1НФ, 2НФ.
Нормальная форма — требование, предъявляемое к структуре таблиц в теории реляционных баз данных для устранения из базы избыточных функциональных зависимостей между атрибутами (полями таблиц).
Процесс преобразования базы данных к виду, отвечающему нормальным формам, называется нормализацией.
Нормализация позволяет обезопасить базу данных от логических и структурных проблем, называемых аномалиями
данных. К примеру, когда существует несколько одинаковых записей в таблице, существует риск нарушения целостности данных при обновлении таблицы. Таблица, прошедшая нормализацию, менее подвержена таким проблемам, т.к. ее структура предполагает определение связей между данными, что исключает необходимость в существовании записей с повторяющейся информацией.
Первая нормальная форма (1NF)
Таблица находится в первой нормальной форме, если каждый её атрибут атомарен и все строки различны. Под выражением «атрибут атомарен» понимается, что атрибут может содержать только одно значение. Таким образом, не соответствуют 1NF таблицы, в полях которых могут храниться списки значений. Для приведения таблицы к 1NF обычно требуется разбить таблицу на несколько отдельных таблиц.
Вторая нормальная форма (2NF)
Таблица находится во второй нормальной форме, если она находится в первой нормальной форме, и при этом любой её атрибут, не входящий в состав первичного ключа, функционально полно зависит от первичного ключа. Функционально полная зависимость означает, что атрибут функционально зависит от всего первичного ключа, но при этом не находится в функциональной зависимости от какой-либо его части.

23. Проектирование БД с использованием теории нормализации. 3НФ, НФБК.
Отношение находится в 3НФ тогда и только тогда, когда оно находится в 2НФ, и для каждого не ключевого атрибута отсутствует транзитивная зависимость от первичного ключа.
Транзитивная зависимость. Если для атрибутов A, B и C некоторого отношения существуют зависимости вида AB и
BC, это означает, что атрибут C транзитивно зависит от атрибута A через атрибут B (при условии, что атрибут А функционально не зависит ни от атрибута B, ни от атрибута C).
Пример. Есть таблица ПОСТАВЩИК (Sid, SName, City, Code). В ней следующие зависимости: Sid  SName, Sid  City, City

Code. Так как код города зависит от города, то выявляется транзитивная зависимость Sid  Code.
Возникают аномалии 3НФ:
• Аномалия вставки: невозможно сохранить данные о новом городе, пока не будет введена запись о новом поставщике с новым городом (первичный ключ не может содержать неопределённые значения);
• Аномалия удаления: при удалении последнего поставщика из данного города теряется информация о городе вообще;
• Аномалия обновления: при изменении кода города или названия города у одного поставщика придётся изменить эти поля у всех поставщиков с данным городом и кодом. Также при изменении кода города придётся изменить и название города, и наоборот – при изменении названия города придётся изменить код города.
Чтобы нормализовать к 3НФ, надо произвести декомпозицию (разбиение) таблицы на две: ПОСТАВЩИК (Sid, SName,
City) и ГОРОД (City, Code).
Нормальная форма Бойса-Кодда (BCNF). Таблица находится в BCNF, если она находится в 3NF, и при этом отсутствуют функциональные зависимости атрибутов первичного ключа от неключевых атрибутов. Таблица может находиться в 3NF, но не в BCNF, только в одном случае: если она имеет, помимо первичного ключа, еще по крайней мере один возможный ключ.
Отношение находится в НФБК тогда и только тогда, когда каждый его детерминант является потенциальным ключом.
Для проверки принадлежности отношения к НФБК необходимо найти все его детерминанты и убедиться в том, что они являются потенциальными ключами. Детерминантом является один атрибут или группа атрибутов, от которой полностью функционально зависит другой атрибут.
Различие между ЗНФ и НФБК заключается в том, что функциональная зависимость АВ допускается в отношении ЗНФ, если атрибут В является первичным ключом, а атрибут А не обязательно является потенциальным ключом. Тогда как в отношении НФБК эта зависимость допускается только тогда, когда атрибут А является потенциальным ключом.
Следовательно, нормальная форма Бойса-Кодда является более строгой версией формы ЗНФ, поскольку каждое отношение НФБК является также отношением ЗНФ, но не всякое отношение ЗНФ является отношением НФБК.
Ситуация, когда отношение будет находиться в 3NF, но не в BCNF, возникает, например, при условии, что отношение
имеет два (или более) потенциальных ключа, которые являются составными и имеют общий атрибут. На практике такая ситуация встречается достаточно редко, для всех прочих отношений 3NF и BCNF эквивалентны.
Отношение находится в нормальной форме Бойса-Кодда (НФБК), если оно находится в 3НФ, и в нем отсутствовали зависимости ключевых атрибутов от неключевых атрибутов

24. Проектирование БД с использованием теории нормализации. Многозначные зависимости. 4НФ.
Нормальная форма — требование, предъявляемое к структуре таблиц в теории реляционных баз данных для устранения из базы избыточных функциональных зависимостей между атрибутами (полями таблиц).
Процесс преобразования базы данных к виду, отвечающему нормальным формам, называется нормализацией.
Нормализация позволяет обезопасить базу данных от логических и структурных проблем, называемых аномалиями
данных. К примеру, когда существует несколько одинаковых записей в таблице, существует риск нарушения целостности данных при обновлении таблицы. Таблица, прошедшая нормализацию, менее подвержена таким проблемам, т.к. ее структура предполагает определение связей между данными, что исключает необходимость в существовании записей с повторяющейся информацией.
Возможность существования в отношении многозначных зависимостей возникает вследствие приведения исходных таблиц к форме 1НФ, для которой не допускается наличие некоторого набора значений на пересечении одной строки и одного столбца. Например, при наличии в отношении двух многозначных атрибутов для достижения непротиворечивого состояния строк необходимо повторить в них каждое значение одного из атрибутов в сочетании с каждым значением другого атрибута. Подобный тип ограничения порождает многозначную зависимость и приводит к избыточности данных.
Многозначная зависимость . Представляет такую зависимость между атрибутами отношения (например, А, B и C), что каждое значение А представляет собой множество значений для A и множество значений для C. Однако множества значений для B и C не зависят друг от друга.
Четвертая нормальная форма (4НФ) - Отношение в нормальной форме Бойса-Кодда, которое не содержит нетривиальных многозначных зависимостей.
Четвёртая нормальная форма (4NF)
Таблица находится в 4NF, если она находится в BCNF и не содержит нетривиальных многозначных зависимостей.
Многозначная зависимость не является функциональной, она существует в том случае, когда из факта, что в таблице содержится некоторая строка X, следует, что в таблице обязательно существует некоторая определённая строка Y.
То есть, таблица находится в 4NF, если все ее многозначные зависимости являются функциональными.

25. Организация доступа к данным. Схема обработки запроса. Способы извлечения данных, методы доступа к данным.
Различают следующие методы хранения и доступа к данным: физический последовательный, индексно- последовательный, индексно-произвольный, инвертированный, метод прямого доступа, метод хеширования.
Физический последовательный
Значения ключей физических записей находятся в логической последовательности. Применяется в основном для дампа и восстановления данных. Может применяться как для хранения, так и для выборки данных.
Эффективность использования памяти близка к 100%. Эффективность физического последовательного метода доступа оставляет желать лучшего, поскольку для выборки нужной записи требуется просмотреть все предыдущие ей записи БД.
Индексно-последовательный
Метод доступа, при использовании которого до осуществления доступа к собственно записям БД проверяются значения ключей, называется индексно-последовательным. Значения ключей физических записей находится в логической последовательности. Может применяться как для хранения, так и для выборки данных. В индекс значений ключей заносятся статьи значений ключей в блоках. Наличие дубликатов значений ключей недопустимо. Эффективность доступа зависит от числа уровней индексации, распределения памяти для размещения индекса, числа записей базы данных и уровня переполнения. Эффективность хранения зависит от размера и изменяемости базы данных.
Индексно-произвольный
При индексно-произвольном методе доступа записи хранятся в произвольном порядке. Создается отдельный файл либо раздел файла БД (в зависимости от СУБД) из статей, содержащих значения действительного ключа и физические адреса хранимых записей.
Значения ключей физических записей необязательно находятся в логической последовательности.
Хранение и доступ к индексу могут осуществляться с помощью индексно-последовательного метода доступа.
Индекс содержит статью для каждой записи БД. Эти статьи упорядочены по возрастанию. Ключи индекса сохраняют логическую последовательность. Записи БД могут быть не упорядочены по возрастанию ключа. Метод может использоваться как для запоминания, так и для выборки данных.
Метод прямого доступа
Основная особенность прямого метода доступа заключается во взаимно однозначном соответствии между ключом записи и ее физическим адресом. Физическое местоположение записи определяется непосредственно из значения ключа. Не требует упорядоченности значений ключей физических записей. Метод может применяться как для хранения, так и для поиска записей. Для поиска одной записи используется одно обращение к индексу.
Наличие дубликатов ключей недопустимо.
Эффективность хранения зависит от плотности ключей. При низкой плотности память расходуется впустую, поскольку резервируются адреса, соответствующие отсутствующим ключам. В ряде случаев не требуется однозначное соответствие между ключом и физическим адресом; записи вполне достаточно, чтобы группа ключей ссылалась на один и тот же физический адрес. Такой метод доступа называется методом доступа посредством хеширования.
Метод доступа посредством хеширования
Хешированием называется метод доступа, обеспечивающий прямую адресацию данных путем преобразования значения ключа в относительный или абсолютный физический адрес. Не требуется логическая упорядоченность значений ключей физических записей. Значениям нескольких ключей может соответствовать один и тот же физический адрес (блок). Может применяться как для хранения, так и для поиска записей.
Эффективность доступа и хранения зависят от распределения ключей, алгоритма их преобразования и распределения памяти. Между методом прямого доступа и методом доступа посредством хеширования существует сходство.
При методе доступа посредством хеширования адрес физической записи алгоритмически определяется из значения ключа записи. Алгоритм преобразования ключа называют также подпрограммой рандомизации. При использовании функции хеширования возможно преобразование двух или более ключей в один и тот же физический адрес, который называется собственным адресом. Записи, ключи которых отображаются в один и тот же физический адрес, называются синонимами, а случай преобразования нового ключа в уже заданный собственный адрес называется коллизией. Поскольку по адресу, определяемому функцией хеширования, может физически храниться только одна запись, синонимы должны

храниться в каких-нибудь других ячейках памяти. При возникновении коллизий образуются цепочки синонимов, необходимых для обеспечения механизма поиска синонимов (рис. 1).
Сущность метода хеширования заключается в том, что все адресное пространство делится на несколько областей фиксированного размера, которые называются бакетами. В качестве бакета может выступать цилиндр, дорожка, блок, страница, т.е. любой участок памяти, адресуемый в операционной среде как единое целое.
Наименьшая составная единицей бакета называется фрагментом записи или секцией. Если при занесении нового значения индекса все бакеты заняты, то для него выделяется дополнительная область памяти, называемая областью переполнения.
Главным ограничением этого метода является фиксированный размер таблицы. Если таблица заполнена слишком сильно или переполнена, то возникнет слишком много цепочек переполнения, и главное преимущество хеширования — доступ к записи почти всегда за одно обращение к таблице — будет утрачено. Расширение таблицы требует ее полной переделки на основе новой хэш-функции (со значением свертки большего размера).
В случае баз данных такие действия являются абсолютно неприемлемыми. Поэтому обычно вводят промежуточные таблицы-справочники, содержащие значения ключей и адреса записей, а сами записи хранятся отдельно. Тогда при переполнении справочника требуется только его переделка, что вызывает меньше накладных расходов.
Характеристики метода:
1. при хеш-файлах распределение ключевых значений оказывает значительное влияние на распределение собственных адресов и количество синонимов;
2. вид функции хеширования оказывает влияние на распределение собственных адресов и на количество синонимов;
3. упорядоченность данных при загрузке данных влияет на общую производительность системы;
4. объем адресного пространства или количество бакетов влияет на количество синонимов и коэффициент резервирования памяти;
5. большой размер бакета обеспечивает гибкость обработки коллизий без использования области переполнения;
6. метод обработки переполнения влияет на время обслуживания и зависит от метода хеширования ключа;
7. хеширование ключа обеспечивает эффективную выборку и обновление записей. Платой за эту эффективность является нарушение логической упорядоченности файла;
8. хеширование допускает возможность вторичного преобразования по специальному ключу.