Способ представления функциональной зависимости

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

Пусть даны числовые множества и .

ОпределениеЕсли каждому элементу x множествапоставлен в соответствие один и только один элемент из множества Y, то говорят, что задано отображение множества и Y или задана функция с областного определения и множеством значений из Y и пишут .

y — значение функции

Обозначают —область определенияфункции

— область значений функции

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

Существует несколько способов задания функции:

1) Аналитический способ,если функция задана формулой вида .

2) Табличный способсостоит в том, что функция задается таблицей, содержащей значения аргумента x и соответствующие значения функции .

3) Графический способсостоит в изображении графика функции.

4) Словесный способ,если функция описывается правилом ее составления.

Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет

Источник

ТОРА (9) — Лекция №2 — Функциональные зависимости

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

Содержание

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

Пусть $R=(A_1 . A_n)$ является функциональной схемой отношения и $X$ , $Y$ — некоторые подмножества атрибутов этой схемы. Говорят, что $X$ функционально определяет $Y$ ( $X\rightarrow Y$ ), если в любом экземпляре отношения со схемой $R$ не существует двух кортежей, совпадающих по подмножеству $X$ и не совпадающих по подмножеству $Y$

Иначе говоря, если два кортежа совпадают по $X$ , то они должны совпадать и по $Y$

Например, $R=(A_1, A_2, A_3, A_4)$ , есть зависимости:

• $A_1\rightarrow A_2$ (1)
• $A_1A_3\rightarrow A_4$ (2)

Предположим, что имеет место один экземпляр отношения со схемой $R$

$A_1$	$A_2$	$A_3$	$A_4$
$R$	фирма X	улица Ленина, д.1	сахар	40
	фирма X	улица Ленина, д.1	карамель	50
	фирма X	улица Ленина, д.2	пастила	90

Вторая ФЗ (2) имеет место быть , так как нет двух кортежей, совпадающих по этой паре (по крайней мере, в приведённом экземпляре схемы отношения, а других мы не знаем).

А первая ФЗ (1) не имеет место быть (в третьей строке другой номер дома портит всю картину).

Замыкание множества функциональных зависимостей

Пусть $R$ — универсальная схема отношения, а $F$ — исходное множество функциональных зависимостей на этой схеме. Замыканием $F$ называется всё множество функциональных зависимостей, которое логически следует из $F$ — обозначается как $F^+$

Функциональная зависимость логически следует из $F$ , если её можно вывести (получить) с помощью аксиом Армстронга.

Аксиомы Армстронга

Или правила вывода функциональной зависимости. Существуют различные интерпретации аксиом, но все эквивалентны. Потому приведём только один вариант.

Аксиомы Армстронга являются надёжными и полными.

Надёжность — если ФЗ выводится с помощью аксиом Армстронга, то она справедлива во всех экземплярах отношения, где справедливы исходные ФЗ $F$

Полнота — если имеет место какая-либо ФЗ, то она обязательно может быть выведена с помощью аксиом Армстронга.

Рефлексивность

Если $Y \subseteq X \subseteq R$

то $X\rightarrow Y$ . Тривиальная аксиома.

Дополнение

Если $X\rightarrow Y$ и $Z \subseteq R$ ( $Z$ может быть пустым),

тогда $X\bigcup Z\rightarrow Y\bigcup Z$ или $XZ\rightarrow YZ$

Транзитивность

Если $X\rightarrow Y$ , а $Y\rightarrow Z$ ,

то $X\rightarrow Z$

Пример построения множества ФЗ

Пусть задана УСО (универсальная схема отношения) $R=(A, B, C)$ и зависимости $F=(A\rightarrow B, B\rightarrow C)$

$A\rightarrow A$ , $B\rightarrow B$ , $C\rightarrow C$ , $AB\rightarrow A$ , $AB\rightarrow B$ , $AC\rightarrow A$ , $AC\rightarrow C$ , $BC\rightarrow B$ , $BC\rightarrow C$ , $ABC\rightarrow A$ , $ABC\rightarrow C$ , $AB\rightarrow AB$ , $AC\rightarrow AC$ , $BC\rightarrow BC$ , $ABC\rightarrow AB$ , $ABC\rightarrow AC$ , $ABC\rightarrow BC$ , $ABC\rightarrow ABC$

$A\rightarrow AB$ (1ФЗ и пополняем A), $AC\rightarrow BC$ , $B\rightarrow BC$ (2 ФЗ и пополняем B), $AB\rightarrow AC$ , $AC\rightarrow ABC$ , $AB\rightarrow ABC$ , $AB\rightarrow BC$ , $A\rightarrow AC$

$A\rightarrow C$ (1 и 2 ФЗ), $A\rightarrow ABC$

Всё, замыкание ( $F^+$ ) построено. Все перечисленные зависимости образуют замыкание.

Лемма

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

Правило объединения

Если $X\rightarrow Y$ и $X\rightarrow Z$ , то $X\rightarrow YZ$

1. $X\rightarrow XY$ (1 ФЗ и пополняем X);
2. $XY\rightarrow YZ$ (2 ФЗ и пополняем Y);
3. $X\rightarrow YZ$ (по аксиоме транзитивности).

Правило декомпозиции

Если $X\rightarrow Y$ , а $Z \subseteq Y$ , то $X\rightarrow Z$

1. $X\rightarrow Y$ (по условию);
2. $Y\rightarrow Z$ (по аксиоме рефлексивности);
3. $X\rightarrow Z$ (по аксиоме транзитивности).

Правило псевдотранзитивности

Если $X\rightarrow Y$ и $WY\rightarrow Z$ , то $WX\rightarrow Z$

1. $WX\rightarrow WY$ (1 ФЗ и пополняем W);
2. $WY\rightarrow Z$ (по условию);
3. $WX\rightarrow Z$ (по аксиоме транзитивности).

Замыкание множества атрибутов

Замыкание $F^+$ может включать в себя очень большое количество ФЗ. Например:

$F=(X\rightarrow A_1, X\rightarrow A_2 . X\rightarrow A_n)$

$X\rightarrow Y \subseteq F^+$

$Y \subseteq (A_1, A_2 . A_n)$ и таких подмножеств может быть $2^n$

Поэтому «в лоб» замыкание $F^+$ никто не строит. Но необходимо найти какой-то метод, который достаточно просто позволял бы выяснять, принадлежит ли произвольная ФЗ $X\rightarrow Y$ к $F^+$

Для этого применяется замыкание множества атрибутов.

Пусть $R$ — универсальная схема отношения, а $X$ — некоторое подмножество атрибутов. Тогда замыканием множества атрибутов $X^+$ называется совокупность атрибутов $A_, A_ . A_$ таких, что $X\rightarrow A_, X\rightarrow A_ . X\rightarrow A_$

Алгоритм построения

Алгоритм является итерационной процедурой.

1. полагаем $i = 0$ и $X_0^+=X$ , а $X_i^+$ — замыкание множества атрибутов на i-том шаге;
2. $X _ ^+ = X _i ^+ \bigcup V$ , где $V$ — такое множество атрибутов в $F$ , что существует ФЗ $Y\rightarrow Z$ , где $Y \subseteq X _i ^+$ , $V \subseteq Z$ ;
3. если $X_^+ = X_i^+$ , то $X^+ = X_i^+$ , иначе $i = i + 1$ и возвращаемся в пункт 2.

Пример построения

Пусть $R=(A, B, C, D, E, G)$

$F=(AB\rightarrow C, C\rightarrow A, BC\rightarrow D, ACD\rightarrow B, D\rightarrow EG, BE\rightarrow C, CG\rightarrow BD, CE\rightarrow AG)$

Надо построить $X^+$ :

1) $i = 0$ , $X _0 ^+ = BD$

$i$	$Y\rightarrow Z$ , для которых $Y \subseteq X_i^+$	$V\subseteq Z$	$X_^+ = X_i^+\bigcup V$
0	$D\rightarrow EG$	$EG$	$BDEG$
1	$BE\rightarrow C$	$C$	$BDEGC$
2	$C\rightarrow A$ $BC\rightarrow D$ $CG\rightarrow BD$ $CE\rightarrow AG$	$A$	$BDEGCA$
3	$AB\rightarrow C$ $ACD\rightarrow B$	—	$BDEGCA$

Получили, что $X_4^+ = X_3^+$ , а значит $X^+ = X_3^+ = BDEGCA$

Это означает, что имеют место следующие ФЗ: $BD\rightarrow B$ , $BD\rightarrow D$ , $BD\rightarrow E$ , $BD\rightarrow G$ , $BD\rightarrow C$ , $BD\rightarrow A$ , и все они $\subseteq F^+$

Короче, чтобы проверить $X\rightarrow Y \subseteq F^+$ , необходимо построить $X^+$

Источник

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

Информация, данные, информационные системы

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

Оставим пока в стороне ответ на вопрос, почему проекты реляционных баз данных бывают плохими, т.е. зачем нужно проектировать реляционную базу данных. Попытаемся сначала ответить на вопросы «В чем заключается проектирование реляционных баз данных ? и «Что лежит в основе процедур проектирования реляционных баз данных ?»

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

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

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

Кортежи отношений могут представлять экземпляры сущности предметной области или фиксировать их взаимосвязь. Но даже если эти кортежи определены правильно, т.е. отвечают схеме отношения и выбраны из допустимых доменов, не всякий из них может быть текущим значением некоторого отношения. Например, возраст человека редко бывает более 120 лет, или один и тот же пилот не может одновременно выполнять два различных рейса. Такие ограничения семантики домена практически не влияют на выбор той или иной схемы отношений . Они представляют собой ограничения на типы данных.

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

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

Определение 1. Пусть r (A₁, A₂, . A_n) — схема отношения R , a X и Y — подмножества r . Говорят, что Х функционально определяет Y , если каждому значению атрибутов кортежа отношения из Х соответствует не более одного значения атрибутов того же кортежа отношения из Y . Такая ФЗ обозначается как .

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

Источник