Файл: Систем управления.pdf

очередь из множества пар атрибут-значение (A
i
:V
i
), (i = 1, 2, ..., n), по одной такой паре для каждого атрибута А. в заголовке. Для любой заданной пары атрибут-значение (A
i
:V
i
) V
i
является значением из единственного домена D
i
, который связан с атрибутом А
i
.
Рис. 2.23. Отношение в реляционной модели
Степень отношения – это число его атрибутов. Отношение степени один называют унарным, степени два – бинарным, степени три – тернарным, ..., а степени п – n-арным.
Кардинальное число или мощность отношения – это число его кортежей. Кардинальное число отношения изменяется во времени в отличие от его степени.
Изменение кардинального числа отношения связано с изменением состояния отношения.
Поскольку отношение – это множество, а множества по определению не содержат совпадающих элементов, то никакие два кортежа отношения не могут быть дубликатами друг друга в любой произвольно-заданный момент времени. Пусть R – отношение с атрибутами А
1
, A
2
, ..., А
п
. Говорят, что множество атрибутов К = (А
i
, А
j
, ..., А
k
) отношения R является возможным ключом R тогда и только тогда, когда удовлетворяются два независимых от времени условия [5].
1. Уникальность: в произвольный заданный момент времени никакие два различных кортежа R не имеют одного и того же значения для А
i
, А
j
, ..., A
k
.
2. Минимальность: ни один из атрибутов А
i
, А
j
, ..., A
k
не может быть исключен из К без нарушения уникальности.
Каждое отношение обладает хотя бы одним возможным ключом, поскольку, по меньшей мере, комбинация всех его атрибутов удовлетворяет условию уникальности. Один из возможных ключей
(выбранный произвольным образом) принимается за его первичный ключ. Остальные возможные ключи, если они есть, называются альтернативными ключами.
Вышеупомянутые и некоторые другие математические понятия явились теоретической базой для создания реляционных СУБД, разработки соответствующих языковых средств и программных систем, обеспечивающих их высокую производительность, и создания основ теории проектирования баз данных. Однако для массового пользователя реляционных СУБД можно использовать неформальные эквиваленты этих понятий:
Отношение – Таблица (иногда Файл),
Кортеж – Строка (иногда Запись),
Атрибут - Столбец, Поле.
52

При этом принимается, что «запись» означает «экземпляр записи», а «поле» означает «имя и тип поля».
Математическое определение реляционной модели приводится в [10, 17].
Отношение рассматривается как подмножество декартова произведения доменов.
Декартовым произведение доменов D
1
, D
2
, ..., D
k
где D
1
={d
1.1
, d
1.2
, …, d
1.i1
, …, d
1.n1
}, D
2
= {d
2.1
, d
2.2
, …, d
2.i2
, …, d
2.n2
},…, Dk = {d
k.1
, d
k.2
, ..., d
k.ik
, ..., d
k.nk
},
называется множество всех кортежей длины k, т.е. состоящих из k элементов – по одному из каждого домена D
i
Пример 2.4. Если D
1
= {A, 2}, D
2
= {B, С}, D
3
= {4, 5, D},то k = 3 и соответственно декартово произведение:
Декартово произведение позволяет получить все возможные комбинации элементов исходных множеств – элементов рассматриваемых доменов.
Отношением R на множествах D
1
, D
2
, ..., D
k
называется подмножество декартова произведения D =
= D
1
×
D
2
×
×
D
k
. Отношение R, определенное на множествах D
1
, D
2
, ..., D
k
(причем не обязательно, чтобы эти множества были различными), есть некоторое множество кортежей арности k: (d
1.i1
, d
2.i2
, ...,
d
i.ik
), таких, что d
1.i1
принадлежит D
1
, d
2.i2
- D
2
и т.д.:
Элементами отношения являются кортежи. Арность кортежа определяет арность отношения.
Поскольку отношение есть множество, то в нем не должны встречаться одинаковые кортежи и порядок кортежей в отношении несуществен.
Отношение может использоваться двояко [17]:
1) для представления набора объектов;
2) для представления связей между наборами объектов.
Для представления набора объектов атрибуты интерпретируются столбцами отношения. Множество допустимых значений атрибута интерпретируется соответствующим доменом. Каждый кортеж отношения выполняет роль описания отдельного объекта из набора. Отношение выполняет роль описания всего набора объектов.
Отношение также используется для представления связей между наборами объектов. В этом случае кортеж в отношении R связь между объектами. Чтобы реализовать такую ситуацию, каждому столбцу отношения ставится в соответствие ключевой атрибут соответствующего набора объектов.
Список имен атрибутов отношения называется схемой отношения. Если отношение называется R и его схема имеет атрибуты с именами А
1
, А
2
, ..., A
k
, то схема отношения
Реляционная база данных – это набор экземпляров конечных отношений. Схему реляционной БД можно представить в виде совокупности схем отношений
53

Другими словами – реляционная база данных – это совокупность отношений, содержащих всю информацию, которая должна храниться в БД. Однако пользователи могут воспринимать такую базу данных как совокупность таблиц. Так на рис. 2.24 показаны таблицы базы данных, построенные по инфологической модели базы данных «Питание» (прил. 4) [5].
1. Каждая таблица состоит из однотипных строк и имеет уникальное имя.
2. Строки имеют фиксированное число полей (столбцов) и значений (множественные поля и повторяющиеся группы недопустимы). Иначе говоря, в каждой позиции таблицы на пересечении строки и столбца всегда имеется в точности одно атомарное значение или ничего.
3. Строки таблицы обязательно отличаются друг от друга хотя бы единственным значением, что позволяет однозначно идентифицировать любую строку такой таблицы.
4. Столбцам таблицы однозначно присваиваются имена, и в каждом из них размещаются однородные значения данных (даты, фамилии, целые числа или денежные суммы).
Рис. 2.24. База данных «Питание» (см. прил.4)
5. Полное информационное содержание базы данных представляется в виде явных значений данных, и такой метод представления является единственным. В частности, не существует каких- либо специальных «связей» или указателей, соединяющих одну таблицу с другой. Так, связи между строкой с БЛ = 2 таблицы «Блюда» на рис. 2.24 и строкой с ПР = 7 таблицы продукты (для приготовления Харчо нужен Рис), представляется не с помощью указателей, а благодаря существованию в таблице «Состав» строки, в которой номер блюда равен 2, а номер продукта – 7.
6. При выполнении операций с таблицей ее строки и столбцы можно обрабатывать в любом порядке безотносительно к их информационному содержанию. Этому способствует наличие имен таблиц и их столбцов, а также возможность выделения любой их строки или любого набора строк с указанными признаками.
2.4.2.4. Достоинства и недостатки даталогических моделей
Сначала остановимся коротко на ранних (дореляционных) СУБД. Ограничимся рассмотрением
54

только общих особенностей ранних систем, а именно, систем, основанных на иерархических и сетевых моделях [8].
1. Эти системы активно использовались в течение многих лет, дольше, чем используется какая-либо из реляционных СУБД. На самом деле некоторые из ранних систем используются даже в наше время, накоплены громадные базы данных, и одной из актуальных проблем информационных систем является использование этих систем совместно с современными системами.
2. Все ранние системы не основывались на каких-либо абстрактных моделях. Как упоминалось, понятие модели данных фактически вошло в обиход специалистов в области БД только вместе с реляционным подходом. Абстрактные представления ранних систем появились позже на основе анализа и выявления общих признаков у различных конкретных систем.
3. В ранних системах доступ к БД производился на уровне записей. Пользователи этих систем осуществляли явную навигацию в БД, используя языки программирования, расширенные функциями
СУБД. Интерактивный доступ к БД поддерживался только путем создания соответствующих прикладных программ с собственным интерфейсом.
4. Навигационная природа ранних систем и доступ к данным на уровне записей заставляли пользователя самого производить всю оптимизацию доступа к БД, без какой-либо поддержки системы.
5. После появления реляционных систем большинство ранних систем было оснащено
«реляционными» интерфейсами. Однако в большинстве случаев это не сделало их по-настоящему реляционными системами, поскольку оставалась возможность манипулировать данными в естественном для них режиме (на низком физическом уровне).
Обобщая перечисленные особенности, можно сформулировать достоинства и недостатки ранних систем.
Достоинства:

развитые средства управления данными во внешней памяти на низком уровне;

возможность построения вручную эффективных прикладных программ;

возможность экономии памяти.
Недостатки:

сложность практического использования;

необходимость знания физической организации данных;

жесткая зависимость прикладных систем от физической организации данных;

логика перегружена деталями организации доступа к БД.
По сравнению с ранними моделями, реляционный подход обладает следующими особенностями [2,
5, 8, 17].
Достоинства:

наличие относительно небольшого набора абстракций;

наличие простого, но мощного математического аппарата (в основе реляционного подхода – теория множеств);

возможность ненавигационного манипулирования данными без знания их конкретной физической организации.
Недостатки:

ограниченность использования в нетрадиционных предметных областях;

относительно неполная адекватность отражения семантики предметной области.
В главе 4 рассматривается самая сильная сторона реляционного подхода – математический аппарат для выполнения операций над отношениями реляционной модели.
Наличие простого, но мощного математического аппарата сыграло решающую роль в повсеместном переходе разработчиков СУБД на реляционную модель.
2.4.3. Нормализация
2.4.3.1. Понятие функциональной зависимости
Создание баз данных преследует две основные цели [2, 10, 17]:

понизить избыточность хранимых данных;

повысить их надежность.
55

Любое априорное знание о различного рода ограничениях, накладываемых на совокупности данных, может принести большую пользу для достижения указанных целей.
Один из способов формализации этих знаний – установление зависимостей между элементами данных. Известно два основных типа таких зависимостей:
1) функциональные зависимости;
2) многозначные зависимости.
Функциональная зависимость является обобщением понятия ключа.
В табл. 2.7 представлено отношение График (ПИЛОТ, РЕЙС, ДАТА, ВРЕМЯ-ВЫЛЕТА). Это отношение показывает, какой пилот участвует в данном рейсе в данный день и каково время вылета самолета. Не любое сочетание значений атрибутов ПИЛОТ, РЕЙС, ДАТА и ВРЕМЯ-ВЫЛЕТА допустимо в таком расписании.
Таблица 2.7
График
ПИЛОТ
РЕЙС
ДАТА
ВРЕМЯ-ВЫЛЕТА
Мовчан
Мовчан
Синицын
Синицын
Синицын
Федотов
Федотов
Вишневский
Вишневский
Вишневский
83 116 281 301 83 83 116 281 281 412 9 августа
10 августа
8 августа
12 августа
11 августа
13 августа
12 августа
9 августа
13 августа
15 августа
10:15 13:25 05:50 18:35 10:15 10:15 13:25 05:50 05:50 13:25
На табл. 2.7 накладываются следующие ограничения.
1. Для каждого рейса назначается только одно время вылета.
2. Для данного пилота, даты и времени вылета возможен только один рейс.
3. Для данного рейса и даты назначается только один пилот.
Эти ограничения являются примерами F-зависимостей (F-зависимость – функциональная зависимость между данными).
F-зависимость имеет место тогда, когда значения кортежа на одном множестве атрибутов
единственным образом определяют эти значения на другом множестве атрибутов.
Указанные выше ограничения можно сформулировать следующим образом.
1. ВРЕМЯ функционально зависит от РЕЙСА.
2. РЕЙС функционально зависит от {ПИЛОТ, ДАТА, ВРЕМЯ}.
3. ПИЛОТ функционально зависит от {РЕЙС, ДАТА}.
Порядок в этих последовательностях могут менять и говорить, что РЕЙС, ДАТА функционально определяют ПИЛОТ, или символически:
Пусть r – отношение со схемой R, X и Y – подмножества R. Отношение r удовлетворяет
функциональной зависимости X → Y, если
В F-зависимости Х → Y подмножество X называется левой частью, а Y – правой частью.
2.4.3.2. Аксиомы вывода функциональных зависимостей
Для отношения r(R) в любой момент существует некоторое семейство F-зависимостей, которым это отношение удовлетворяет. Здесь может возникнуть та же проблема, что и с ключами: одно состояние отношения может удовлетворять F-зависимости, а другое – нет.
Требуется выявить семейство F-зависимостей F, которому удовлетворяют все допустимые состояния
56

r. Чтобы найти F, необходимы семантические знания об отношении r. Поэтому можно считать семейство F-зависимостей заданным в схеме отношения R, в этом случае любое отношение r(F) должно удовлетворять всем F-зависимостям из F. Не всегда ясно, что является первичным: множество допустимых состояний отношения, которое определяет F-зависимости, или F-зависимости накладывают ограничения на схему отношения [10].
Множество функциональных зависимостей, применимых к отношению r(R), конечно, так как существует только конечное число подмножеств множества R. Таким образом, всегда можно найти все
F-зависимости, которым удовлетворяет r. Однако этот подход требует большого количества шагов и, соответственно, много времени.
Если известны некоторые F-зависимости из F, то часто можно вывести остальные.
Множество F-зависимостей F влечет за собой зависимость X → Y, если каждое отношение, удовлетворяющее всем зависимостям в F, удовлетворяет также зависимости X → Y.
Аксиома вывода - это правило, устанавливающее, что если отношение удовлетворяет определенным
F-зависимостям, то оно должно удовлетворять и некоторым другим F-зависимостям.
Сформулировано шесть аксиом вывода F-зависимостей [10]. В этих формулировках используется обозначение r для отношения на R и W, X, Y и Z – для подмножеств R.