Базы данных

Если запись найдена, то:

а) если записи не закреплены >бит свободен/занят в состояние свободен (при следующем добавлении субблок будет использован);

б) если записи закреплены >бит свободен/занят не изменяется, а бит удалён установить в состояние 1- удалён.

Если записи не закреплены, то возможно для удаления использовать следующий алгоритм > последнюю запись файла переписать на место удаленной, а последний субблок освободить.

21. Анализ методов доступа к хешированным файлам

Проблема реорганизации. Анализ временных характеристик хеширования.

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

Если каждый участок состоит ровно из одного блока (т.е. лучший случай) для поиска требуется 2 обращения, для остальных 3. Чтобы уменьшить число блоков в участках нужно число участков должно быть ? числу записей в файле/ на число записей в блоке.

При росте числа блоков требуется реорганизация. Её достаточно просто провести, если ввести два ограничения:

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

При реорганизации число участков n умножают на некоторое фиксированное с (обычно с = 2).

Если мы удвоим число участков, то все записи участка i будут попадать в участки i или i+n и в эти участки не попадут никакие записи других участков.

Пусть по ключу v построим N=h(v) и N >>n- числа участков (если мы удвоим n то получим N >>2n), разделим N на n и получим (1.) ; где: k-целое, i-остаток от деления, 0 ?i ?n-1 номер участка. Из формулы 1: (2.) N= nk+i;

Удвоив число участков получим: (3.) ; формулу (1.) разделим на 2 и прировняем с (3.) (4.) ;

Рассмотрим два случая.

k=2l четное (5.) ;

в формуле (5.) - равенство двух смешанных чисел, l и m - целые числа, таким образом это целая часть смешанны числа равны > равны и целые части l = m , и равны и дробные частит.о. номер нового участка совпадает с номером старого участка.

k=2l+1 нечетное; (6.) ; (7.) ; (8.) ;

l=m > j=n+i,т.е. новый участок сдвинут по отношению к старому на n.

Таким образом при удваивании числа участков записи, находившейся в участке i будут находится или в участке i или в участке i+ n, где n-старое число участков.

Индексированные файлы.

Решается та же задача: поиск записи по ключу v.

Допустим, что записи в файле отсортированы по значениям этого ключа (обратить внимание на сортировку дат dtos() и строк - лексикографическая сортировка). Для нескольких полей: сортировка по первому ключу, при равных первых - сортировка по второму и т.д.

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

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

Пара (v,b) появляется в файле индекса, если первая запись в блоке главного файла с адресом b имеет значение ключа v. Записи файла индекса подобно обыкновенному (информационному) файлу с двумя полями : ключ и номер блока. Записи файла индекса отсортированы по значению ключа и не являются закрепленными, т.к. нигде в другом файле нет ссылки ни на какую запись файла индекса. Вероятно, что с файлом индекса, как и с обычным (информационным) файлом следует выполнить операции включения, модификации, удаления и кроме того необходима новая функция (вместо поиска): для данного ключа v, найти такую запись ((v2 ,b2)| (v2 ? v1) ? ((следующая (v3,b3) | (v3 >v1) ? (v2,b2) -последняя в файле)))

В этом случае говорят, что v2 перекрывает v1 (это значит, что если запись с ключом v1, содержится в файле, то она может содержаться только в блоке b2, у которого первая запись имеет ключ v2).

3. Поиск в индексе.

Требуется найти запись в основном файле с ключом v1.

Задача (для файла индекса): найти в файле индекса запись (v2,b2) такую, что v2 покрывает ключ v1.

Решение: В простом случае (мало записей в индексе) - линейный поиск (условия применения - весь индекс в основной памяти) Внимание! пояснить, что такое линейный поиск.

Но и в этом случае выигрыш, т.к. если в блоке основного файла записано 'к' записей и известно 1 запись в индексе организуется на первый блок основного файла, то в файле индекса в 'к' раз меньше записей. Кроме того, обычно записи индекса короче, чем записи основного файла и в 1 блок индекса помещается больше записей (появляется вероятность размещение всего индекса в оперативной памяти).

Лучшая стратегия поиска в файле индекса - использование двоичного поиска. При данной стратегии на каждом шаге количество блоков (при поиске записи (v2,b2) - покрывающих ключ v1) индекса, содержащих запись (v2,b2) сокращается вдвое.

Таким образом если в индексе n блоков, то не боле чем за log2(n+1) чтений будет прогнан блок индекса, содержащий запись (v2,b2). В практике часто вместо оценки log2(n+1) используют оценку log2n. С учетом доступов к основному файлу общее число доступов - 3+ log2n (3 складывается из 1 - чтение справочника индекса, 1 - чтение блока файла, 1 - запись блока файла).

Пример: Пусть в главном файле есть 106 записей. В блоке помещается 10 записей, следовательно всего в файле 105 блоков. Пусть в один блок индекса помещается 100 записей, значит для индекса необходимо 1000 блоков. Таким образом, для доступа и перезаписи блока основного файла требуется 3+ log21000?13 обращений (log21024 = log2210 = 10, т.о. log21024?log21000?10).

При исследовании хешированного файла (и условии 1 блок - 1 участок) необходимо 3 доступа, но имеется для индекса дополнительные преимущества ? возможность поддерживать отсортированный порядок в файле (как минимум логическую упорядоченность).

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

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

24. Операции над сортированным файлом с незакрепленными записями и неплотным индексом

Операции над сортированным файлом с незакрепленными записями.

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

Поиск записи: (найти запись с ключом v)

в индексе найти запись (v2,b2), где v2 покрывает v1;

прочитать блок b2 в оперативную память и искать запись с ключом v1 в оперативной памяти каким-нибудь методом (двоичным или линейным). Если найдено, то успешно.

При поиске проверять биты свободен/занят, удален/не удален.

Модифицирование:

найти запись с ключом v1, если нет то выход;

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

Включение: (добавить запись с ключом v1)

новую запись надо добавить в 1 блок. v1 меньше, чем первая запись первого блока значит первую запись в индексе надо изменить;

если v2?v1не в первый блок, тогда в начало среднего блока никогда не добавится; v2<v1 запись не будет первой; если v2=v1, то аварийный останов.

Т.о. если добавляется не в 1 блок, то файл индекса никогда не изменяется. Еще при добавлении: - есть место в блоке - добавили и все; - если места в блоке нет, тогда добавление новой записи в ОП в данный блок нужно отсортировать в порядке и дальше этот блок делят: последнюю запись выталкивают в следующий блок, следовательно, индекс модифицируется. Обработка последнего блока - выталкивать некуда, тогда надо взять у OS новый блок.

Удалить: (запись с ключом v1)

найти запись с ключом v1, если не найдена, то ошибка;

запись найдена, то удаление производится сдвигом влево, начиная с записи следующей за удаленной. Установка бита свободен/занят в состояние свободен. Если удаляется первая запись в блоке, то корректируется индекс. Если после удаления блок полностью пустой, то вернуть блок в OS и удалить запись из индекса. Если она последняя и первая, то блок главного файла вернуть в OS и удалить 1 запись из индекса.

Использование цепных файлов при индексной организации.

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

Организация сортированных файлов с закрепленными записями.

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

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

Рассмотрим операции над таким файлом.

Инициализация: процедура формирования файла индекса по первоначальному главному файлу называется - инициализацией.

Для инициализации отсортируем файл и распределим его записи по блокам. При этом в каждом блоке выделим некоторое свободное пространство (несколько свободных субблоков) которые при добавлении записи исключат на некоторое время рост цепочек в участках главного файла. Кроме того, предусмотрим один пустой блок в участке, предшествующем первому, куда будем помещать записи при расширении файла, и которые будут предшествовать записям первоначального файла. Создадим индекс для полученного файла, в том числе и для пустого блока. Запись в индексе для этого блока должна содержать номер «пустого» блока и не содержать ключа.

Поиск: найти запись с ключом v1.

Найдем запись индекса, значение ключа которой покрывает требуемое значение ключа v1. Если v1 меньше, чем первое значение ключа в файле индекса (заметим, что первичный ключ находится во второй записи индекса), то требуемой записью индекса является первая запись. По указателю на блок (из индекса) читаем первый блок цепочки (участка). Чтобы найти ключ v1 просматриваем блоки данного участка, соединенных в цепочку.

Модификация: аналогично предыдущей.

Включение: добавить запись с ключом v1.

Поиск участка по ключу v1 . Просмотрим блоки участка, с целью найти свободное место. Если свободного субблока нет, то получим из OS пустой блок и добавим его в конец участка (пояснить). Включим новую запись в новый блок.

Удаление: поиск записи с ключом v1. Если запись найдена, то установка бита удален в состояние «1» (запись удалена). Если данная запись не закреплена установка бита свободен/занят в состояние свободен.

25. Основные понятия реляционных СУБД

Объект - сущность предметной области.

Атрибут (имя Атрибута, реквизит) - параметр объекта предметной области. (Свойство некоторой сущности).

Пример: Фамилия, Возраст - свойства объекта сотрудник.

Домен (атрибута) - множество допустимых значений, которые может принимать атрибут.

Пример: значение атрибута Возраст должно принадлежат интервалу [18…80]

Схема отношения - конечное множество [имен] атрибутов, определяющих объект. (Мощность схемы отношения = арности кортежей.)

Отношение - конечное множество кортежей (подмножество прямого произведения), составленных из допустимых значений атрибутов схемы отношений.

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

Схема реляционной базы - множество используемых в приложениях схем отношений.

Реляционная база данных (РБД) - множество отношений (предполагается, что отношения логически связаны между собой). 

Реляционные операции - операции над отношениями. Результатом любой реляционной операции является также отношение. 

Реляционное выражение - выражение над отношениями, составленное из реляционных операций. Реляционное выражение - тоже отношение.

Реляционный запрос - описание свойств (условий), которые должны удовлетворять интересующие пользователя данные.

Эквивалентной формой описания запроса является реляционное выражение.

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

Язык описания данных (ЯОД, DDL) - язык, позволяющий описать структуру БД и создать БД с требуемой структурой.

Язык манипулирования данными (ЯМД, DML) - язык, позволяющий описать действия по чтению, добавлению, обновлению и удалению данных в БД.

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

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

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

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

Примером ограничения диапазонов является определение доменов атрибутов. Примером структурного ограничения является определение ключей.

Транзакция - неделимая операция по изменению содержания БД. Выполнение транзакции завершается двумя способами:

отмена транзакции (возврат в предыдущее состояние);

регистрация транзакции: проверка и, при необходимости, восстановление целостности БД.

Итак, до и после выполнения транзакции база данных гарантированно находится в целостном состоянии. В течение выполнения транзакции целостность базы данных не контролируется.

Защита баз данных - это:

защита БД от физических и логических разрушений;

обеспечение санкционированного доступа к данным.

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

26. Основные реляционные операции

база данные сервер хеширование

Операция объединения (соединения) - объединение множества кортежей двух отношений в одно общее отношение. Операция определена для двух отношений одинаковой арности.

Пусть R и S - отношения арности n. 

Объединение R?S = { (V1,V2 … Vn) ¦(V1…Vn)R ?(V1 … Vn)S }

Операция разности отношений - разностью двух отношений арности n называется отношение (арности n), в которую включены кортежи первого отношения, не принадлежащие одновременно второму отношению.

Пусть R и S - отношения арности n. 

Разность: R - S = {(V1 … Vn) | (V1 … Vn)R ? (V1 … Vn)?S}

Операция декартового произведения - двух отношений R (арности n), и S (арности m) называется отношение арности m+n, кортежи которого составлены из кортежей R и S.

Пусть R - отношение арности n, S - отношение арности m.

Декартовое произведение для R= {(V1 … Vn)} и S= {(W1 … Wm)} это:

RхS = {(V1…Vn, W1…Wm) ¦ (V1…Vn)R?(W1…Wm)S}

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

Пусть R - отношение арности n, обозначим рi1,i2…im (R) - проекцию R на атрибуты i1, i2, …im, где 1 ? ij ? n, 1 ? j ? m

Проекция: рi1,i2…im (R) = {(a1 … am) | ? (b1 … bn) R | aj = bij ? j = 1 … m }

Пример: проекция р2,1(R) - составлена из значений второго и первого элемента схемы отношения R.

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

Пусть F (предикат на множества атрибутов) - логическая формула, в которую входят:

константы;

имена атрибутов;

функции;

операции арифметических отношений <, >, ?, ??, =;

логические операции ?,?,¬.

Селекцией отношения R по формуле F - это отношение: дF(R )={(V1…Vn)R| F?1}

Естественное соединение.

Пусть отношение А имеет атрибуты{X1, X2…Xm, Y1, Y2…Yn}, а отношение В {Y1, Y2…Yn, Z1, Z2, …Zk}.

Атрибуты Y1, Y2 … Yn, и только они являются общими для этих отношений. Пусть атрибуты с одинаковыми именами определены на одних и тех же доменах.

Для простоты множества атрибутов обозначим буквами: X,Y,Z

Естественным соединением А и В (A Join B) называется отношение с атрибутами X, Y, Z, состоящими из кортежей (x, y, z), таких, для которых в отношении А атрибуты X=x?Y=y, при этом в отношении В атрибуты Y=y?Z=z.

(A Join B) JoinС = A Join (B Join C)

Пример: А = {код, имя, статус, город} - поставщики, В = {номер, вес, город} - детали

Отношение A

Код	Имя	Статус	Город
1	Иванов	20	Москва
2	Петров	10	Казань
3	Сидоров	30	Казань
4	Семенов	20	Москва
5	Конкин	30	Новгород

Отношение В

Номер	Вес	Город
1	12	Москва
2	17	Казань
3	17	Ростов
4	14	Москва
5	12	Казань
6	19	Москва

Отношение A Join B

Код	Имя	Статус	Город	Номер	Вес
1	Иванов	20	Москва	1	12
1	Иванов	20	Москва	4	14
1	Иванов	20	Москва	6	19
2	Петров	10	Казань	2	17
2	Петров	10	Казань	5	12
3	Сидоров	30	Казань	2	17
3	Сидоров	30	Казань	5	12
4	Семёнов	20	Москва	1	12
4	Семёнов	20	Москва	4	14
4	Семёнов	20	Москва	6	19

Другие примеры операций над отношениями:

R

A	B	C
a	b	c
d	a	f
c	b	d

S:

D	E	F
b	g	a
d	a	f

R ? S:

a	b	c
d	a	f
c	b	d
b	g	a

?

Схему необходимо выбрать дополнительно

R - S:

a	b	c
c	b	d

R ? S



A	B	C	D	E	F
a	b	c	b	g	a
d	a	f	b	g	a
c	b	d	b	g	a
a	b	c	d	a	f
d	a	f	d	a	f
c	b	d	d	a	f

?A,C (R):

A	C
a	с
d	f
c	d

дB=b (R )

A	B	C
a	b	c
c	b	d

27. Правила Кодда (требования к реляционным БД)

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

Перечислим эти правила:

Явное представление данных.

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

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

Гарантированный доступ к данным.

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

а) имени отношения;

б) указателя на кортеж (например, значение первичного ключа кортежа);

в) имени атрибута;

(имя_отношения, первичный ключ, атрибут)

Полная обработка неопределенных значений.

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

Доступ к базе данных в терминах реляционной модели.

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

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

Реляционная схема может поддерживать несколько языков, по крайней мере, язык DDL и DML. Однако хотя бы один из языков должен иметь синтаксис предложений, поддерживающий следующие понятия:

определение данных (отношения, атрибуты, домены, ключи, ограничения целостности);

определение виртуальных (мнимых) отношений, образованных с помощью реляционных выражений на основе одного или нескольких отношений (определение представлений);

манипулирование данными (интерактивное или программное);

ограничение целостности;

санкционированный доступ;

управление транзакциями (начало транзакции, фиксация выполнения, отказ от выполнения).

Обновляемость представлений.

Все представления (виртуальные отношения) должны автоматически обновляться при модификации данных в базовых отношениях. Если, например, A= R ? S, и А - это представление, то А должно обновляться как только меняется R или S.

Наличие высокоуровнего языка манипулирования данными.

Операции вставки, обновления и удаления должны применяться к отношению в целом:

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

Физическая независимость данных.

Прикладные программы не должны зависеть от используемых способов хранения данных на носителях информации и методов доступа к ним.

Физически независимые обеспечивает работоспособность приложений при изменении расположения данных в сети.

Логическая независимость данных.

Прикладные программы не должны зависеть от реализации любого из используемых представлений (виртуальных отношений).

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

Независимость контроля целостности.

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

Дистрибутивная независимость.

Реляционная система должна быть распространяема и переносима. Создание разнородных компьютерных систем требует обеспечения доступа к базам данных в различных OS и на различных платформах.

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

Согласования языковых уровней.

Если реляционная система имеет низкоуровневый язык доступа (элемент доступа - запись) и высокоуровневый язык доступ (элемент доступа - отношения). То выполнение низкоуровневых команд должно производиться с контролем целостности, так же, как и при высокоуровневых командах.

28. Отношения и реляционная алгебра

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

Переменной отношение - это абстрактное понятие, под которым мы будем понимать произвольное отношение (для некоторых операций произвольное отношение с определенной схемой (заголовком отношения)).

Для того чтобы задать значение отношения необходимо задать:

Схему отношения (заголовок отношения), как множество атрибутов, точнее множество пар вида ( < имя_ атрибута >, < имя_ домена >).

Множество кортежей (тело отношения).

Каждый кортеж - упорядоченное множество. С каждым значением в кортеже связано имя атрибута, т.е. кортеж можно понимать, как множество пар (<имя _ атрибута>, <значение _атрибута>).

В нашем курсе мы будем рассматривать отношения, обладающие следующими свойствами:

В отношениях нет одинаковых кортежей.

Кортежи неупорядочены.

Атрибуты неупорядочены (т.е. атрибуты именованы).

Все значения атрибутов - атомарные (скалярные).

Пояснения:

атрибут является атомарным, если его невозможно разбить на более простые части, которые соответствуют каким-то параметром объекта из предметной области.

Очень часто свойства 1…3 в конкретных языках СУБД нарушаются.

Пример: Допускается, чтобы кортежи повторялись, вводится упорядоченность кортежей и атрибутов в кортеже. Т.е. есть операция перейти на первый кортеж, на следующий кортеж прочитать атрибут № 5.

Требование упорядоченности обусловлено требованиями базового языка, а не реляционной модели. Заметим, что для конечного пользования свойство упорядоченности скрыто.

Примеры неатомарных атрибутов:

1. База данных сотрудников. Есть атрибут дети: список: пар (имя ребенка, год рождения)

2. Атрибут ФИО можно иногда рассматривать как атомарный атрибут, иногда как множество их 3-х атрибутов:

Фамилия;

Имя;

Отчество;

29. Алгоритм нормализации отношения до 1 НФ

Рассмотрим на примере: R1: = {A, RA2 } RA2: = {C, D}

Найдём ?А(R1) = {A} = {{ai}}, {ai} - множество значений атрибута А.

Найдём ?RA2(R1) = {RA2} = {{C,D}} - ?A=ai (R1) - кортеж для аi.

Найдём ?RA2 (?A=?ai(R1)) - отношение RA2 для кортежа А=аi

R = ?А(R1) ? ?RA2(?A=ai(R1))

Задача: Разработать другой алгоритм.

Пример нормализации отношения

Отношение Сотрудники.

№	Фамилия	Должность	Оклад	Дети
1.	Иванов	Директор	100	Оля 1990 Маша 1992
2.	Петров	Гл. инженер	100	Сережа 1989 Катя 1991 Коля 1995

Нормализованная база.

№	Фамилия	Должность	Оклад	Имя	Год рождения
1	Иванов	Директор	100	Оля	1990
1.	Иванов	Директор	100	Маша	1992
2.	Петров	Гл. инженер	100	Сережа	1989
2.	Петров	Гл. инженер	100	Катя	1991
2.	Петров	Гл. инженер	100	Коля	1995

- первичный ключ

30. Виды отношений, используемых в реляционных системах

Именованное отношение - это переменная типа отношение, у которой есть имя.

Базовое отношение - это именованное отношение, которое не является производным от других отношений.

Производное отношение - это отношение, определённое через другие именованные отношения (посредством реляционного выражения), и в конечном итоге через базовые отношения.

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

Каждое именованное отношение является выражаемым отношением, но необязательно, что выражаемое отношение имеет имя.

Множество всех выражаемых отношений - это объединение множества всех базовых отношений и множества всех производных отношений.

Представление - это именованное производное отношение. Представление (как и базовое явление, переменным отношениями).

Снимки - это именованные производные отношения (являются переменными отношениями). Создание снимка похоже на выполнение запроса, за исключением того, что результат такого запроса сохраняется в базе данных под некоторым именем как отношение, доступное только для чтения. Периодически (например,: раз в сутки) снимок обновляется.

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

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

Хранимое отношение - это отношение, которое поддерживается во внешней памяти.

31. Целостность БД и потенциальные ключи

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

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

Любое правило целостности является специфическим для данной БД.

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

Потенциальный ключ - это обобщение понятия первичного ключа. Первичный ключ уникальным образом идентифицирует кортеж в отношении.

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

Определение потенциального ключа:

Пусть R - некоторая переменная отношения, тогда потенциальный ключ K для R это подмножество атрибутов R, всегда обладающее следующими свойствами:

Свойство уникальности: нет двух различных кортежей в текущем значении переменной R с одинаковыми значениями K

Свойство не избыточности: никакое из подмножеств K не обладает свойством уникальности.

На практике чаще всего встречается 1 потенциальный ключ, который выбирается первичным.

Пример: дана БД элементов таблицы Менделеева: порядковый номер элемента, атомная масса, название элемента и т.д. - все это потенциальные ключи.

Потенциальный ключ - множество (атрибутов).

Потенциальный ключ из 1-го атрибута - это простой ключ.

Потенциальный ключ из нескольких атрибутов - это составной ключ.

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

32. Целостность БД и внешние ключи

Пусть R2 - базовое отношение, тогда внешний ключ, например, FK в отношении R2 - это подмножество множества атрибутов R2, такое что:

существует базовое отношение R1 (R1 и R2 не обязательно различны) с потенциальным ключом СК;

каждое значение FK в текущем значении R2 всегда совпадает со значением СК некоторого кортежа в текущем значении R1.

Замечания:

внешний ключ - это множество (вводят через {}), но если внешний ключ простой, то скобки могут опускаться;

каждому значению внешнего ключа соответствует значение потенциального ключа (обратно не справедливо).

Пример: цвет автомобиля в таблице Auto это указатель на значение цвета, который храниться в таблице menu.

В теории реляционных баз данных требуется:

Если внешний ключ составной, то соответствующий потенциальный ключ тоже составной. Если внешний ключ простой, то потенциальный ключ тоже простой.

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

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

Значение внешнего ключа является ссылкой на кортеж, содержащий соответствующее значение потенциального ключа (так называемый ссылочный или целевой кортеж). Проблема обеспечения того, что база данных не должна включать никаких неверных значений внешних ключей называемой проблемой ссылочной целостности. Ограничение, по которому каждое значение внешнего ключа должно соответствовать значению потенциального ключа, называется ссылочным ограничением. Отношение, которое содержит внешнюю ссылку, называется ссылающимся отношением, а отношение, которое содержит потенциальный ключ - ссылочным или целевым отношением.

Ссылочные ограничения представляются ссылочными диаграммами. Иногда над стрелкой пишут внешний ключ.

C_COLOR

AUTO ? MENU

Отношение (R2) может быть одновременно и ссылочным, и ссылающимся

R3? R2?R1

Отношение может ссылаться само на себя

R1? R1

Пример: Список сотрудников, у которых есть атрибут - код сотрудника, которому данный сотрудник подчиняется

Ссылки могут образовывать цикл (ссылочный цикл)

Rn ? Rn-1 … R1 ? Rn

Заметим, что атрибут(ы) становится внешним ключом, если имеется отношение с соответствующим ему потенциальным ключом.

Ссылочная целостность.

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

Удаление в ссылающемся отношении никогда не нарушает ссылочную целостность.

Проверить ссылочную целостность в момент добавления или коррекции ссылающегося отношения не является сложным. Вся сложность лишь в предоставлении возможности добавить кортеж в ссылочное отношение из среды работы с ссылающимся отношением.

Добавление в ссылочное отношение никогда не нарушает ссылочную целостность.

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

Если при выполнении этих операций нарушается ссылочная целостность, то используют две основные стратегии.

операции, нарушающие целостность, отвергнуть;

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

Пример: удалить или изменить кортежи ссылающейся базы.

При этом 2-й вариант реализации возможен при организации диалога с пользователем (предложить изменить ссылающиеся отношения, удаляемая запись перенести в архив и т.д.).

Особая сложность возникает при наличии ссылочных циклов. Возможно, проверку ссылочной целостности следует отложить до момента фиксации транзакции.

33. Первичные ключи и Null значения

Вместе с понятием первичного ключа модель включает правило целостности объекта, которое заключается в следующем:

Ни один элемент первичного ключа базового отношения не может быть Null - значением.

Предпосылки введения такого правила следующие:

кортежи базового отношения соответствует объектам реального мира;

объекты реального мира различны (т.е. некоторым образом опознаваемы);

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

Если первичный ключ или его часть имеет Null - значение ? идентичность объекту теряется.

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

Проблема использования Null - значений до конца ещё не решена. Введение и поддержка этого правила имеет несколько противоречий.

Пример: допустим, что в базе AUTO мы ввели понятие Null - значение для атрибута код_ цвета. Составим список цветов автомобилей. В этом списке (отношении) возможно, будет значение - цвет не определён. Наш запрос не является базовым отношением. И для него требования целостности объекта может не применяться. Но что возникнет, если результат запроса мы сохраним как базовое отношение. Такое отношение состоит только из одного атрибута - цвет, которое должно быть первичным ключом.

Альтернативной стратегией Null - значениям является использование значений по - умолчанию.

34. Внешние ключи и Null значения

Не вызывает особых сомнений, что внешние ключи могут принимать Null - значения. 

Пример: если рассмотреть самоссылающееся отношения <сотрудники>, в котором есть атрибут <код_начальника>, то у президента компании -- это атрибут содержит Null - значение. Т.о. понятие внешнего ключа должно быть дополнено возможностью принимать значение Null.

Следовательно, определение внешнего ключа должно быть расширено:

Пусть R2 - базовое отношение. Тогда внешний ключ FK в отношении R2 - это подмножество множества атрибутов R2, такое что:

Существует базовое отношение R1 (R1 и R2 не обязательно различны) с потенциальным ключом СК.

Всегда каждое значение FK в текущем значении R2 или является Null - значением, или совпадает со значением СК некоторого кортежа в текущем значении R1

Возможность включения или не включения Null - значений в первичные и внешние ключи регулируются соответствующими опциями операторов языка определения БД.

Замечание: Допустимость принятия Null - значения для внешнего ключа решает (каким - то образом) проблему ссылочной целостности.

Пример: при удалении некоторого цвета из справочника цветов достаточно у автомобилей (база AUTO), у которых был удаляемый цвет, установить цвет в Null.



35. Проектирование баз данных

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

- логическое проектирование;

- физическая реализация;

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

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

Теория проектирования в полном объеме недостаточно формализована, т.о. процесс проектирования в большой степени является все-таки искусством.

Проектирование БД - это не единственное условие получения правильной структуры организации данных.

Второе условие - это условие описания и проверки целостности БД.

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

Задача логического проектирования - фактически сводится к тому, чтобы решить какие базовые отношения и с какими атрибутами следует использовать в проекте.



36. Функциональные зависимости. Определения и примеры

Определение функциональных зависимостей даётся в двух видах:

Для значения элементов отношений в некотором времени.

Для всевозможных значений элементов отношения.

Определение функциональных зависимостей первого типа:

Пусть R -- отношение. X и Y некоторые подмножество множества его атрибутов. Тогда Y функционально зависимо от Х. Тогда и только тогда, когда каждому элементу множества Х соответствует один и только один элемент множества Y. Функциональную зависимость записывают так: X?Y. Иначе: Y функционально зависит от X, если два кортежа отношения R совпадают по множеству атрибутов Х, то они совпадают по множеству атрибутов Y.

Пример: Рассмотрим отношение R1 с множеством атрибутов

A={Поставщик, Город, Товар, Количество}

Поставщик	Город	Товар	Кол-во
1	Москва	1	100
1	Москва	2	100
2	Саратов	1	200
2	Саратов	2	200
3	Таганрог	2	300
4	Ростов	2	400
4	Ростов	4	400
4	Ростов	5	400

Выпишем ФЗ, которые существуют в R1 (при этих значениях)

поставщик>город

(поставщик, товар)>количество

(поставщик, товар)>город

(поставщик, товар)>(город, количество)

(поставщик, товар)>поставщик

(поставщик, товар)>(поставщик, товар, город, количество)

(поставщик)>количество

(количество)>поставщик

В ФЗ левая часть называется детерминантом, а правая - зависимой частью.

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

Предположим, что ФЗ поставщик>город справедлива для любого значения переменной отношения R1, т.е. справедлива в любой момент времени. Фактически это является ограничением целостности БД. В жизни этому соответствует то, что никакая компания не имеет филиалов.

Определения функциональных зависимостей второго типа: Пусть R - является переменной отношения, а X и Y являются произвольными подмножествами множества атрибутов отношения R. Говорят, что Y функционально зависит от X тогда и только тогда, когда для любого допустимого значения отношения R каждому значению атрибутов, имена которых находятся во множестве X, соответствует одно и только одно значение атрибутов, имена которых находятся во множестве Y. Иначе: для любого допустимого значения отношения R, если два кортежа отношения R совпадают по значению атрибутов, имена которых находятся во множестве X, то они совпадают по значениям атрибутов, имена которых находятся во множестве Y.

Пример: поставщик ? город . Это означает, в предметной области есть ограничение «поставщики не имеют филиалов». Если два кортежа совпадают по коду поставщика, то эти кортежи обязательно совпадут по городу, в котором расположен поставщик.

Наличие функциональной зависимости определяется внешней моделью предметной области.

Например, если дополнительно предположить, что поставщик не может дважды поставить один и тот же товар, то функциональные зависимости будут таковыми:

(поставщик, товар)>количество;

(поставщик, товар)>(город, количество);

(поставщик, товар)>поставщик;

(поставщик, товар)>(поставщик, товар, город, количество);

поставщик>город;

Очевидно, что для любого значения отношения не выполняются: поставщик>количество; количество>поставщик. По определению 2 они не является ФЗ, но выполняются в примере функциональных зависимостей первого типа.

38. Функциональные зависимости и целостность БД

ФЗ фактически является условиями ограничения целостности. Т.о. их необходимо проверять при обновлении данных в СУБД. Пусть множество таких ФЗ обозначается S. Если таких зависимостей много, то их сложно проверить. Т.о. возникает задача получить такое множество Т, которое было бы гораздо меньшего размера, чем исходное множество S. Причём каждая ФЗ из S могла бы быть заменена условиями из Т. Поиск такого множества ФЗ представляет большой практический интерес.

ФЗ тривиальна тогда и только тогда, когда правая часть символической записи данной зависимости является подмножеством левой части. Исключения тривиальных зависимостей сокращает множество ФЗ.

39. Замыкание множества зависимостей. Правила Армстронга

Из некоторых ФЗ могут быть получены другие ФЗ.

Пример: (A, B)?(C, D) ? (A, B)?C, (A, B)?D.

Пусть дано некоторое множество функциональных зависимостей S.

Определение: Множество всех ФЗ, которые могут быть получены из данного множества S, называют замыканием множества зависимостей (S+). Чтобы получить множество S+ используют правила вывода функциональных зависимостей (правила АМСТРОНГА).

Пусть А,В,С,D - произвольные подмножества некоторого множества реквизитов отношения R. Запись АВ означает А?В (для краткости).

Правила Армстронга.

Рефлексивность В?А=>А>В.

Дополнение (А>В)=>АС>ВС.

Транзитивность (А>В)?(В>С)=>(А>С).

Самоопределение (А>А).

Декомпозиция (А>ВС)=>(А>В)?(А>С).

Объединение (А>В)?(А>С)=>А>ВС.

Композиция (А>В)?(С>D)=>(АС>ВD)

Доказательство правил выполняется на основании определения функциональной зависимости. Правила 1..3 называются основными правилами. Они являются необходимыми и достаточными для получения из множества S замыкание множества S+. Для удобства используют правила 4..7, которые называются вспомогательными.

Пример: Пусть R={a,b,c,d,e,f}, где а - номер сотрудника, b - номер отдела, c - номер руководителя, d - номер проекта, e - название отдела, f - доля времени, уделяемая руководителем данному проекту.

S={{a}>{b,c}, {b}>{e}, {c,d}>{e,f}}

Доказать: {a,d}>{f}

Доказательство:

{a}>{b,c}=>{a}>{b}8{a}>{c}=>{a}>{c}=>{a,d}>{c,d}8{c,d}>{e,f}=>{a,d}>{e,f}=>{a,d}>{e}8{a,d}>{f}=>{a,d}>{f}, что и требовалось доказать.

Замечание: Правила Армстронга позволяют получить замыкание множества ФЗ, но не дают алгоритм как это сделать.

40. Замыкание множества атрибутов. Суперключи

Суперключом отношения R называется множество атрибутов отношения R, которое содержит как подмножество хотя бы один потенциальный ключ (т.е. ключ, который обладает свойствами: 1 - уникальности, 2 - не избыточности). Суперключ обладает свойством уникальности, но является избыточным.

Пусть дано переменная отношения R с множеством атрибутов A. Допустим, что для некоторого подмножества K множества атрибутов A (K?A), выполняется ФЗ K>A. По определения ФЗ это означает, что если два кортежа отношения R совпадают по значениям атрибутов из множества K, то эти два кортежа будут совпадать и по значениям атрибутов A, т.е. по множеству всех атрибутов. Но в этом случае (два кортежа совпадают по K) эти два кортежа просто совпадают, что невозможно, т.к. в отношении никакие два кортежа не могут совпадать. Следовательно, никакие два кортежа не могут совпадать по значению атрибутов из множества K. При условии, что K>A в этом случае K обладает свойством уникальности и значит, что K- это ключ.

Суперключи - это такие подмножества Кi (Ki?A) множества атрибутов отношения R, обладающее свойством уникальности и избыточности. Это значит, что у Кi есть непустое подмножество, не совпадающее с Кi (например, K?Кi), обладающее свойством уникальности, т.е. K>A.

Пусть известно некоторое множество S функциональных зависимостей отношения R. Требуется найти потенциальные ключи этого отношения. Если построить множество всех ключей (каждый из элементов этого множества содержит потенциальный ключ) и исключить из этого множества суперключи (т.е.ключи, обладающие свойством избыточности), то мы получим множество потенциальных ключей. Чтобы установить является ли множество атрибутов Кi ключом необходимо выяснить являются ли функционально зависимыми все атрибуты отношения R от Ki, т.е. если для отношения R, с множеством атрибутов А, множеством ФЗ S и множеством Ki ? A удается найти множество Кi+ ? А такое, что все элементы Кi+ функционально зависят от Кi и при этом Кi+ = А, то Кi является ключом. Если при этом ключ не обладает избыточностью, то это потенциальный ключ.

Множество всех элементов из A, функционально зависимых от Ki ? A, называется замыканием множества Ki для отношения R и множества функциональных зависимостей S и обозначается Ki+ ? A. Если для Ki построили Ki+ , то выполняется ФЗ Ki>Ki+.

41. Алгоритм построения замыкания множества атрибутов. Проверка выполнения свойств суперключа. Построение потенциальных ключей

Дано: отношение R с множеством атрибутов A и множеством ФЗ S={X1>Y1,X2>Y2,...,Xm>Ym}. Кроме того, пусть дано подмножество атрибутов Ki ? A. Построим Ki+, замыкание множества ФЗ Ki. Т.е. требуется построить множество всех атрибутов из A, которые функционально зависят от Ki (т.е. Ki>Ki+). Алгоритм построения такого множества является рекуррентным. В качестве начального приближения Ki+ выберем само множество Ki. Это возможно, т.к. имеет место ФЗ Кi > Кi и, следовательно, Ki ? Ki+ . Итак:

Ki+ = Ki

Цикл_пока истина

j = 0, f = ложь

Цикл_пока j < m

j + +

Если (Xj ? Ki+ ) ? ( ? y?y ? Yj ? y ? Ki+ )

Ki+ = Ki+ ? Yj

f = истинна

Всё_если

Всё_цикл

Если не (f) то

Выход из цикла

Всё_если

Всё_цикл

Пример: Дано: отношение R, А - множество атрибутов, А = {a, b, c, d, e, f},

S = {{a} ? {b, c}, {e} ? {c, f}, {b} ? {e}, {c, d} ? {e, f}}

Найти: {a, b}+ для {a, b}

{a, b}+ = {a, b}

Бесконечный цикл

Цикл по элементам множества S

а) {a} ? {b, c} {a} ? {a,b}+ => {a, b}+ = {a, b} ? {b, c} = {a, b, c}

б) {e} ? {c, f} {e} {a, b}+ => {a, b}+ = {a, b, c}

в) {b} ? {e} {b} ? {a,b}+ {a, b}+ = {a, b, c} ? {e} = {a, b, c, e}

г) {c, d} ? {e, f} {c, d} {a, b}+ => {a, b}+ = {a, b, c, e}

а) {a, b}+ = {a, b, c, e}

б) {e} ? {c, f} {e} ? {a, b}+ => {a, b}+ ={a, b, c, e} ? {c, f}={a, b, c, e, f}

Далее {a, b}+ не изменится и т. о. {a, b}+ = {a, b, c, e, f}. Мы построили такое множество {a, b}+, которое зависит от {a, b}, т.е. {a, b} ? {a, b, c, e, f}.

Множество {a, b}+ ? A и {a, b} не является ключом и, т.о. не является ни потенциальным ключом, ни суперключом.



42. Следствие из алгоритма построения замыкания для множества атрибутов. Упрощение множества функциональных зависимостей

Пусть дано:

Отношение R с множеством атрибутов A

Множество ФЗ S для R и S={X1>Y1,X2>Y2,...,Xm>Ym}.

Некоторая ФЗ X ? Y такая, что X ? Y ? S.

Проверить: {X ? Y} ? S+. Т.е. необходимо проверить: следует ли X ? Y из S или нет.

Решение:

Построим для {R, S, X} замыкание X+ для множества атрибутов X.

Каждый элемент (атрибут) множества X+ функционально зависим от X, т.е. X?X+.? Следовательно, любое подмножество X+ функционально зависимо от X. И, если Y ? X+, то X ? Y следует из S и, тогда, {X ? Y} ? S+ ? истина.

Если Y X+ , то функциональная зависимость X ? Y не следует из S и {X ? Y} S+.

Алгоритм проверки, следует ли Ф.З. X?Y из множества S, т.е. проверки принадлежности X ? Y множеству S+.

Для R, S построить X+

Если Y ? X+ то

{X ? Y} ? S+

иначе

{X ? Y} S+

все - если.

Пример: Дано: A = { a, b, c, d, e, f }

S = {{ a } ? { b, c }, { b } ? { e }, { c, d } ? { e, f }

Найти: истинность высказывания ({ a, d } ? { f } ? S+ )

Решение: обозначим x = { a, d } и найдем X+

X+ = { a, d }

X+ = { a, b, c, d }

X+ = { a, b, c, d, e }

X+ = { a, b, c, d, e, f }

Следовательно, в ФЗ {a,d}?{f} зависима часть {f}?{a, d}+, т.о. {{a, d}?{f}}?S+

43. Неприводимое множество зависимостей

Пусть S1 и S2 два множества зависимостей отношения R. Если S1+ ? S2+, то говорят, что S2 является покрытием S1. Это означает, что, если выполняются накладываемые на отношение ограничения S2, то будут выполняться и ограничения S1.

Если S1 покрытие S2, а S2 является покрытием S1, т.е. S1+ = S2+, то S1 и S2 называют эквивалентными множествами ФЗ.

Это означает, что, если выполняются ограничения S1, то выполняются ограничения S2, и наоборот.

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