Если А -» В, то АС -» В (С произвольно).

Стр 1 из 7Следующая ⇒

РЕЛЯЦИОННАЯ МОДЕЛЬ ДАННЫХ.

Определение модели данных предусматривает

· указание множества допустимых информационных конструкций

· множества допустимых операций над данными

· множества ограничений для хранимых значений данных.

Классификация информационных конструкций (информационных объектов) тесно связана с областью их использования в ЭИС:

1. Объекты для технологии баз данных - отношения и веерные отношения.

2. Объекты для технологии искусственного интеллекта - предикаты, фреймы и семантические сети.

3. Объекты для технологии мультимедиа - тексты, графические изображения, фонограммы и видеофрагменты.

Реляционная модель данных характеризуется следующими компонентами:

• информационной конструкцией - отношением с двухуровневой структурой,

• допустимыми операциями - проекцией, выборкой, соединением и некоторыми другими,

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

Каждому классу объектов Р материального мира ставится в соответствие некоторое множество атрибутов, например А1, А2,...,Ап. Отдельный объект класса Р описывается строкой величин (al, а2,.... an), где ai - значение атрибута Ai.

Строка (al, a2,..., an) называется КОРТЕЖЕМ. Всему классу объектов соответствует множество кортежей, называемое ОТНОШЕНИЕМ. Обозначим отношение, описывающее класс объектов Р, также через Р.

Выражение Р(А1, А2,...,Ап) называется СХЕМОЙ ОТНОШЕНИЯ.

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

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

• строке таблицы соответствует кортеж отношения,

• все строки таблицы (и соответственно все кортежи) различны,

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

КОМПОНЕНТЫ СХЕМЫ РЕЛЯЦ-Й БД:

S(rel) = <A,R,Dom,Rel,V(s)>,

где А - множество имен атрибутов,

R - множество имен отношений,

Dom - вхождение атрибутов в домены,

Rel - вхождение атрибутов в отношения,

V(s) - множество ограничений (в том числе функциональных зависимостей).

Множество отношений и операций над ними образует реляционную алгебру.

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

T = R[X],

где R - исходное отношение,

Т - результирующее отношение,

X - список атрибутов в структуре отношения Т (условие проекции).

ПРИМЕР

Рассмотрим два отношения: W1, содержащее сведения о продаже продукции в 1998 г., и W2, в котором указаны цены на продукцию и комплектующие изделия для соответствующих видов продукции.

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

XI = W1 [Магазин, Продукция, Факт]

и имеет вид:

Столбцы результирующего отношения могут указываться в любом порядке:

Х2 = W1 [Продукция, Магазин, Факт]

Следующий ПРИМЕР проекции - это получение справочника Х1 цен на продукцию:

Х2=W2[продукция, цена]

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

1. Условие вида Имя_атрибута <знак сравнения> Значение, где допускаются знаки сравнения =, #, >, =>, <, <=. Например, Цена > 100.

2. Условие вида Имя_атрибута_1 <знак сравнения> Имя_ _атрибута_2. Например, Факт > План.

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

T = R[p],

где R - исходное отношение;

Т - результирующее отношение;

р - условие выборки.

Пример:

Х5= Wl[Продукция = "Эдв-12"]

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

Обозначим исходные отношения через R1 и R2, а результирующее – Т.

ОБЪЕДИНЕНИЕ Т = U(R1, R2) содержит строки, присутствующие либо в отношении R1, либо в R2.

ПЕРЕСЕЧЕНИЕ Т = I(R1, R2) содержит строки, присутствующие в отношениях R1 и R2 одновременно.

ВЫЧИТАНИЕ Т = M(R 1, R2) содержит те строки из R1, которые отсутствуют в R2.

ОПЕРАЦИЯ СОЕДИНЕНИЯотношений выполняется над двумя исходными отношениями и создает одно результирующее. Каждая строка первого исходного отношения сопоставляется по очереди со всеми строками второго отношения, и если для этой пары строк соблюдается условие соединения, то они сцепляются и образуют очередную строку в результирующем отношении. Условие соединения имеет вид:

Имя_атрибута_1 <знак сравнения> Имя_атрибута_2,

где Имя_атрибута_1 находится в одном исходном отношении, а Имя_атрибута_2 - в другом. Будем использовать следующее обозначение операции соединения:

T = Rl[p]R2,

где RI и R2 - исходные отношения,

Т - результирующее отношение,

р - условие соединения.

Наиболее важный частный случай соединения называется НАТУРАЛЬНЫМ СОЕДИНЕНИЕМи имеет следующие особенности:

• знаком сравнения в условии соединения является "=",

• Имя_атрибута_1 и Имя_атрибута_2 должны совпадать, а точнее, содержать пересечение списков атрибутов исходных отношений,

• список атрибутов результирующего отношения образуется в результате объединения списков атрибутов исходных отношений.

Обозначение натурального соединения не содержит условия соединения и имеет вид

Т = Rl * R2

Если требуется сведения о продаже продукции из отношения W1 дополнить данными о ценах на продукцию из отношения Х7, то задача решается с помощью соединения:

Х8 = Wl[ Продукция = Продукция ]Х7

Операция натурального соединения имеет ряд свойств, например коммутативность и ассоциативность.

СВОЙСТВО КОММУНИКАТИВНОСТИозначает, что операции X1=R*SHX2=S*R порождают, в сущности, одно и то же отношение.

СВОЙСТВО АССОЦИАТИВНОСТИозначает, что операция Y1=(R*S)*T и операция Y2=R*(S*T) дают одинаковый результат.

ОПЕРАЦИИ ДЕЛЕНИЯ ОТНОШЕНИЙ.

ПРИМЕР:

Пусть существует отношение У(ФИО, ЯП), где для каждого программиста с фамилией ФИО указываются языки программирования ЯП, которые он знает.

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

XI1 = Y[ ЯП = "Си" AND ЯП = "Фортран"]

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

Определим операцию, называемую "образ". В отношении Т(А,В) образом значения а атрибута А является множество значений атрибута В, и каждый элемент b этого множества образует вместе с а некоторую строку (или часть строки) отношения Т.

im В(а) = {Ы,Ь2,..., bk},

где im - знак операции "образ",

а - значение, образ которого вычисляется,

В - имя атрибута для образа значения а,

Ь1, Ь2,...,Ьк - значения атрибута В.

Стоящая перед нами задача решается путем вычисления образов значений "Си" и "Фортран" и последующего пересечения найденных образов.

im ФИО("Си") = {"Иванов","Петров","Семин"}

im ФИО("Фортран") = {"Иванов","Семин","Яшин"}

1тФИО("Си") ∩ im ФИО("Фортран")= {"Иванов","Семин"}

Результатом операции деления является отношение Q(B), содержащее пересечение образов всех строк отношения-делителя V(A), вычисленных на основе отношения-делимого W(A,B)

Q = D (W,V),

где D - знак операции деления.

НОРМАЛИЗАЦИЯ ОТНОШЕНИЙ

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

Рациональные варианты группировки должны учитывать следующие требования:

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

• корректировка отношений не должна приводить к двусмысленности или потере информации,

• перестройка набора отношений при добавлении в базу данных новых атрибутов должна быть минимальной.

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

Отношение в первой нормальной форме (сокращенно 1НФ) - это обычное отношение с двухуровневой структурой. Недопустимость в структуре отношения третьего и последующих уровней является ограничением, определяющим 1 НФ отношения. Преобразование ненормализованного отношения в представление, соответствующее 1НФ, - это ОПЕРАЦИЯ НОРМАЛИЗАЦИИ.

ФУНКЦИОН-Е ЗАВИС-ТИ И КЛЮЧИ

Функциональные зависимости определяются для атрибутов, находящихся в одном и том же отношении, удовлетворяющем 1НФ.

В отношении R(A,B,...) атрибут А функционально определяет атрибут В, если в любой момент времени

каждому значению А соответствует единственное значение В (обозначается А -> В). Отсутствие функциональной зависимости обозначается А —/—> В.

Рассмотрим простой пример с атрибутами ФИО и ГР (год рождения) в отношении R1.

Предположим, что в столбце ФИО представлены сведения о разных людях и соответствующие значения в столбце не повторяются. Тогда можно утверждать наличие функциональной зависимости ФИО -» ГР, поскольку каждому значению атрибута ФИО в отношении RI соответствует единственное значение атрибута ГР. Можно утверждать, что это ограничение будет соблюдаться и далее, так как оно перефразируется в утверждение: у каждого человека единственный sod рождения, которое справедливо.

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

Одновременное соблюдение двух зависимостей вида А -> В и В —> А называется взаимно-однозначным соответствием и обозна

чается А ß-> В.

ПРИМЕР:

Одновременное соблюдение двух зависимостей вида А -> В и В —> А называется взаимно-однозначным соответствием и обозначается А ß--> В

ПРИМЕР:

отношение R2 с атрибутами Магазин и Расч (номер расчетного счета).

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

Магазин ->Расч и Расч -> Магазин, т.е. Магазин ß--> Расч

Cамыми распространенными являются случаи отсутствия функциональных зависимостей/

ПРИМЕР:

ФИО —/-» Дисциплина и Дисциплина —/-» ФИО в отношении R3, описывающем экзамены студентов. Здесь каждый студент сдает экзамены по нескольким дисциплинам, и по каждой дисциплине экзамен сдается многими студентами.

Таким образом, для атрибутов А и В некоторого отношения возможны следующие ситуации:

• отсутствие функциональной зависимости,

• наличие А —> В (или В ->А), но не обе зависимости вместе,

• наличие взаимно-однозначного соответствия А<-> В.

Понятие функциональной зависимости распространяется на ситуацию с тремя и более атрибутами в следующей форме. Группа атрибутов (для определенности А,В,С) функционально определяет атрибут D в отношении T(A,B,C,D,....), если каждому сочетанию значений <а,Ь,с> соответствует единственное значение d (а - значение A, b - значение В, с - значение С, d - значение D). Наличие такой функциональной зависимости будем обозначать А,В,С -> D.

Пусть в отношении Т1 представлены сведения о закончившихся экзаменах.

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

ФИО, Дата -» Дисциплина,

ФИО, Дата -» Преподаватель,

ФИО, Дата -> ОЦЕНКА

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

Рассмотрим в качестве примера отношение ТЗ (имена и значения атрибутов - условные):

Можно утверждать, что вероятным ключом отношения ТЗ является атрибут ZEN (значения в столбце ZEN не повторяются). Кроме того, еще один вероятный ключ представлен парой атрибутов RAM, AST.

ПЕРВИЧНЫМ КЛЮЧОМ отношения называется такой вероятный ключ, по значениям которого производится контроль достоверности информации в отношении.

ся по известным функциональным зависимостям.

Каждое значение первичного ключа встречается только в одной строке отношения. Значение любого атрибута в этой строке также единственное. Если через К обозначить атрибуты первичного ключа в отношении R(A,B,C,... J), то справедливы следующие функциональные зависимости К -> А, К -> В, К -> С,..., К -> J.

Набор атрибутов первичного ключа функционально определяет любой атрибут отношения. Обратное также верно: если найдена группа атрибутов, которая функционально определяет все атрибуты отношения по отдельности, и эту группу нельзя сократить, то найден первичный ключ отношения.

Вернемся к отношению Т1 с функциональными зависимостями:

ФИО, Дата -» Дисциплина,

ФИО, Дата -» Преподаватель,

ФИО, Дата -» Оценка.

Нетрудно установить, что

ФИО, Дата -» ФИО,

ФИО, Дата -» Дата

(в каждом сочетании значений ФИО, Дата значение ФИО встречается один раз). Следовательно, первичный ключ в отношении Т1 составляют атрибуты ФИО, Дата и при поиске ключа не потребовались конкретные значения Т1.

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

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

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

ТЕОРЕМА 1

А,В -> А и А,В -> В.

Доказательство основано на том, что в строке <а,Ь> для атрибутов А и В значение а (как и значение Ь) присутствует один раз.

ТЕОРЕМА 2

А -» В и А -» С т. и т. т., к. А -» ВС.

Рассмотрим произвольное значение а атрибута А. Если А-»ВиА-»С, Toim В(а) и im С(а) содержат по одному элементу. Предположим, что зависимость А -» ВС неверна и im ВС(а) состоит из 2 или более элементов. Тогда либо im B(a), либо im C(a) должны содержать более одного элемента. Полученное

противоречие доказывает зависимость А -> ВС.

Обратно, если А -» ВС, то im BC(a) содержит один элемент вида <Ь,с> для любого а. Зафиксируем некоторое значение al. Значение b (как и значение с) встречается в сочетании с al только один раз, следовательно, справедливо А —• В и А -> С.

ТЕОРЕМА 3

Если А -> В и В -»С, то А -»С.

Предположим, что зависимость А -> С неверна и множество im C(a) содержит более одного элемента. Каждому значению а соответствует единственное значение b (в силу А -» В), поэтому im C(b) содержит более одного элемента. Получилось противоречие с условием В -* С, что и доказывает теорему. Примечательно, что доказательства остальных теорем опираются на первые 3 теоремы, а не доказываются от противного.

ТЕОРЕМА 4

Если А -» В, то АС -» В (С произвольно).

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

АС -» А (теорема 1), А -» В (условие), следовательно, АС -» В по теореме 3.

ТЕОРЕМА 5

Если А -» В, то АС -> ВС (С произвольно).

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

АС -> В (теорема 4), АС -* С (теорема 1), следовательно, АС-» ВС по теореме 2.

ТЕОРЕМА 6

Если А -> В и ВС -> D, то АС -» D.

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

Из А -> В следует АС -> ВС (теорема 5). ВС -» D (условие), поэтому АС -»D по теореме 3.

Для некоторого множества функциональных зависимостей F введем множество F~, называемое покрытием.

ПОКРЫТИЕ F~ содержит все функциональные зависимости, которые можно получить из множества F в результате применения теорем 1- 6 (включая и содержимое F). Одно и то же покрытие F~ может

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

Среди таких множеств выделим множество с минимальным числом зависимостей и назовем его МИНИМАЛЬНЫМ ПОКРЫТИЕМ(БАЗИСОМ) множества зависимостей F. Иначе можно сказать, что

минимальным покрытием называется множество функциональных зависимостей, из которого удалены все зависимости, являющиеся следствиями оставшихся зависимостей и теорем 1-6.

ОТНОШЕНИЕ ИМЕЕТ 2НФ, если оно соответствует 1НФ и не содержит неполных функциональных зависимостей.

НЕПОЛНАЯ ФУНКЦИОН-Я ЗАВИСИМОСТЬ - это две зависимости:

• вероятный ключ отношения функционально определяет некоторый неключевой атрибут,

• часть вероятного ключа функционально определяет этот же неключевой атрибут.

Отношение, не соответствующее 2НФ, характеризуется избыточностью хранимых данных.

Например:

Функциональные зависимости отношения Т4:.

(1) Магазин, Изделие -» План_1999_г.,

• (2) Изделие -» Цена.

Вероятным ключом в Т4 являются атрибуты Магазин, Изделие.

Для доказательства можно сослаться на функциональные зависимости:Магазин, Изделие -»План_1999_г.,

(3) Магазин, Изделие -» Цена (теорема 4),

(4) Магазин, Изделие -» Магазин (теорема 1),

(5) Магазин, Изделие -» Изделие (теорема 1).

Зависимости (3) и (2) вместе образуют неполную функциональную зависимость, по этой причине отношение Т4 находится лишь в 1НФ, а не во 2НФ.

Избыточность иллюстрируется тем фактом, что цена изделия указывается столько раз, сколько магазинов продают это изделие (изделие М22 в Т4). Переход к 2НФ и соответственно устранение отмеченной избыточности данных связано с созданием двух отношений вместо исходного отношения Т4.

Т41=Т4[Магазин,Изделие, План_1999_г.],

Т42=Т4[Изделие,Цена].

Ключом в Т41 служат атрибуты Магазин, Изделие, в Т42 - Изделие, и легко определить, что оба отношения соответствуют требованиям 2НФ.

База данных находится в 2НФ, если все ее отношения находятся в 2НФ.

Дата добавления: 2018-05-12; просмотров: 437; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 3 4 5 6 7 Следующая ⇒

Мы поможем в написании ваших работ!