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

В реляционных баз данных теории функциональная зависимость — это следующее ограничение между двумя наборами атрибутов в отношении : Учитывая отношение R и наборы атрибутов. $X,Y\subseteq R$ , что X Говорят функционально определяет Y (записывается X → Y ), если и только если каждое значение X связано ровно с одним Y. значением удовлетворяет Тогда говорят, что функциональной зависимости X → Y. R Эквивалентно, проекция $\Pi _{X,Y}R$ является функцией есть Y является функцией от X. , то ^[1]^[2] Проще говоря, если значения атрибутов X известны (скажем, это x ), то значения атрибутов Y , соответствующих x, можно определить, просматривая их в любом кортеже R , содержащем x . Обычно X называют детерминантным множеством, а Y — множеством зависимым . Функциональная зависимость FD: X → Y называется тривиальной если Y является подмножеством X , .

Другими словами, зависимость FD: X → Y что значения Y определяются значениями X. означает , Два кортежа, имеющие одинаковые значения X обязательно будут иметь одинаковые значения Y. ,

Определение функциональных зависимостей является важной частью проектирования баз данных в реляционной модели , а также нормализации и денормализации баз данных . Простым применением функциональных зависимостей является теорема Хита ; он говорит, что отношение R над набором атрибутов U и удовлетворяющее функциональной зависимости X → Y можно безопасно разделить на два отношения, обладающие свойством разложения соединения без потерь , а именно на $\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)=R$ где Z = U − XY — остальные атрибуты. ( Объединения наборов атрибутов в теории баз данных обычно обозначаются сопоставлениями.) Важным понятием в этом контексте является потенциальный ключ , определяемый как минимальный набор атрибутов, которые функционально определяют все атрибуты в отношении. Функциональные зависимости вместе с атрибутивными доменами выбираются так, чтобы генерировать ограничения, исключающие больше данных, не соответствующих пользовательскому домену из системы как можно .

Понятие логической импликации определяется для функциональных зависимостей следующим образом: совокупность функциональных зависимостей $\Sigma$ логически подразумевает другой набор зависимостей $\Gamma$ , если какое-либо отношение R, удовлетворяющее всем зависимостям от $\Sigma$ также удовлетворяет всем зависимостям от $\Gamma$ ; обычно это пишут $\Sigma \models \Gamma$ . Понятие логической импликации функциональных зависимостей допускает здравую и полную конечную аксиоматизацию , известную как аксиомы Армстронга .

Примеры

Автомобили

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

Эта функциональная зависимость может предполагать, что атрибут EngineCapacity будет помещен в связь с потенциальным ключом VIN. Однако это не всегда может быть уместно. Например, если эта функциональная зависимость возникает в результате транзитивных функциональных зависимостей VIN → VehicleModel и VehicleModel → EngineCapacity, то это не приведет к нормализации отношения.

Лекции

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

Студенческий билет	Семестр	Лекция	ОБЛИЦОВКА
1234	6	Численные методы	Джон
1221	4	Численные методы	Смит
1234	6	Визуальные вычисления	Боб
1201	2	Численные методы	Питер
1201	2	Физика II	Саймон

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

StudentID → Отпуск.

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

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

{StudentID, Лекция} → ТА
{StudentID, Лекция} → {TA, Семестр}

Последнее выражает тот факт, что набор {StudentID, Lecture} является суперключом отношения.

Модель отдела сотрудников

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

Идентификатор сотрудника	Имя сотрудника	Идентификатор отдела	Название отдела
0001	Джон Доу	1	Человеческие ресурсы
0002	Джейн Доу	2	Маркетинг
0003	Джон Смит	1	Человеческие ресурсы
0004	Джейн Гудолл	3	Продажи

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

Идентификатор сотрудника → Имя сотрудника
Идентификатор сотрудника → Идентификатор отдела

Помимо этой связи, таблица также имеет функциональную зависимость через неключевой атрибут.

Идентификатор отдела → Название отдела

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

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

Учитывая, что X , Y и Z являются наборами атрибутов в отношении R , можно вывести несколько свойств функциональных зависимостей. Среди наиболее важных можно выделить следующие, обычно называемые аксиомами Армстронга : ^[3]

Рефлексивность : если Y является подмножеством X , то X → Y
Увеличение : Если X → Y , то XZ → YZ.
Транзитивность : если X → Y и Y → Z , то X → Z.

«Рефлексивность» можно ослабить всего лишь до $X\rightarrow \varnothing$ , то есть это действительная аксиома , где два других являются собственными правилами вывода , точнее, порождающими следующие правила синтаксической последовательности: ^[4]

$\vdash X\rightarrow \varnothing$
$X\rightarrow Y\vdash XZ\rightarrow YZ$
$X\rightarrow Y,Y\rightarrow Z\vdash X\rightarrow Z$ .

Эти три правила представляют собой здравую и полную аксиоматизацию функциональных зависимостей. Эту аксиоматизацию иногда называют конечной, поскольку число правил вывода конечно. ^[5] с оговоркой, что аксиома и правила вывода являются схемами , а это означает, что X , Y и Z варьируются по всем основным терминам (наборам атрибутов). ^[4]

Применяя аугментацию и транзитивность, можно вывести два дополнительных правила:

Псевдотранзитивность : если X → Y и YW → Z , то XW → Z. ^[3]
Состав : Если X → Y и Z → W , то XZ → YW. ^[6]

также можно вывести Правила объединения и разложения из аксиом Армстронга: ^[3]^[7]

X → Y и X → Z тогда и только тогда, когда X → YZ

Закрытие

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

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

Данный $R$ и $F$ набор FD, который содержится в $R$ :Закрытие $F$ в $R$ (обозначается $F$ ⁺) — это набор всех ФД, которые логически подразумеваются $F$ . ^[8]

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

Замыкание множества атрибутов X относительно $F$ это множество X ⁺ всех атрибутов, которые функционально определены X, используя $F$ ⁺.

Пример

Представьте себе следующий список ФД. Мы собираемся вычислить замыкание для A (записанное как A ⁺) из этого отношения.

А → Б
Б → С
АВ → Д

Закрытие будет следующим:

A → A (по рефлексивности Армстронга)
A → AB (по 1. и (a))
A → ABD (по (b), 3 и транзитивности Армстронга)
A → ABCD (по (c) и 2)

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

Покрытия и эквивалентность

Обложки

Определение : $F$ обложки $G$ если каждый ФД в $G$ можно сделать вывод из $F$ . $F$ обложки $G$ если $G$ ⁺ ⊆ $F$ ⁺
Каждый набор функциональных зависимостей имеет каноническое покрытие .

Эквивалентность двух наборов ФД

Два комплекта ФД $F$ и $G$ о расписании $R$ эквивалентны, написаны $F$ ≡ $G$ , если $F$ ⁺ = $G$ ⁺. Если $F$ ≡ $G$ , затем $F$ это прикрытие для $G$ и наоборот. Другими словами, эквивалентные множества функциональных зависимостей называются покрытиями друг друга.

Нерезервированные крышки

Набор $F$ FD не является избыточным, если нет надлежащего подмножества $F'$ из $F$ с $F'$ ≡ $F$ . Если такой $F'$ существует, $F$ является излишним. $F$ является неизбыточным покрытием для $G$ если $F$ это прикрытие для $G$ и $F$ является неизбыточным.
Альтернативная характеристика неизбыточности состоит в том, что $F$ нет ФД X → Y. неизбыточен, если в нем $F$ такой, что $F$ -{ Икс → Y } $\models$ Икс → Y. Вызовите СД X → Y в $F$ избыточен в $F$ если $F$ -{ Икс → Y } $\models$ Х → Y.

Приложения к нормализации

Теорема Хита

Важным свойством (дающим немедленное применение) функциональных зависимостей является то, что если R является отношением со столбцами, названными по некоторому набору атрибутов U и R, удовлетворяет некоторой функциональной зависимости X → Y , то $R=\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)$ где Z знак равно U - XY . выполняется функциональная зависимость X → Y Интуитивно понятно, что если в R , то отношение можно безопасно разбить на два отношения рядом со столбцом X (который является ключом для $\Pi _{XY}(R)\bowtie \Pi _{XZ}(R)$ ) гарантируя, что при обратном соединении двух частей данные не будут потеряны, т. е. функциональная зависимость обеспечивает простой способ построить без потерь на разложение R два меньших отношения. Этот факт иногда называют теоремой Хита ; это один из первых результатов в теории баз данных. ^[9]

Теорема Хита фактически утверждает, что мы можем извлечь значения Y из большого отношения R и сохранить их в одном: $\Pi _{XY}(R)$ , который не имеет повторений значений в строке для X и фактически представляет собой таблицу поиска для Y с ключом X и, следовательно, имеет только одно место для обновления Y, соответствующего каждому X, в отличие от «большого» отношения R , где потенциально существует много копий каждый X , каждый со своей копией Y , которую необходимо синхронизировать при обновлениях. (Такое устранение избыточности является преимуществом в контекстах OLTP , где ожидается много изменений, но не так много в контекстах OLAP , которые включают в себя в основном запросы.) Декомпозиция Хита оставляет только X в качестве внешнего ключа в оставшейся части большой таблицы. $\Pi _{XZ}(R)$ .

Однако функциональные зависимости не следует путать с зависимостями включения , которые представляют собой формализм внешних ключей; даже несмотря на то, что функциональные зависимости используются для нормализации, они выражают ограничения по одному отношению (схеме), тогда как зависимости включения выражают ограничения между схемами отношений в схеме базы данных . Более того, эти два понятия даже не пересекаются в классификации зависимостей : функциональные зависимости — это зависимости, генерирующие равенство , тогда как зависимости включения — это зависимости, генерирующие кортежи . Обеспечение соблюдения референциальных ограничений после декомпозиции (нормализации) схемы отношений требует нового формализма, то есть зависимостей включения. В разложении, следующем из теоремы Хита, ничто не препятствует вставке кортежей в $\Pi _{XZ}(R)$ имеющее некоторое значение X, не найденное в $\Pi _{XY}(R)$ .

Нормальные формы

Нормальные формы — это уровни нормализации базы данных , которые определяют «качественность» таблицы. Обычно третья нормальная форма считается «хорошим» стандартом для реляционной базы данных. ^{[ нужна ссылка ]}

Цель нормализации — освободить базу данных от аномалий обновления, вставки и удаления. Это также гарантирует, что когда новое значение вводится в отношение, оно оказывает минимальное влияние на базу данных и, следовательно, минимальное влияние на приложения, использующие базу данных. ^{[ нужна ссылка ]}

Неприводимая функция, зависящая от множества

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

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

Наборы функциональных зависимостей, обладающие этими свойствами, называются также каноническими или минимальными . Нахождение такого набора S функциональных зависимостей, который эквивалентен некоторому входному множеству S', предоставленному в качестве входных данных, называется поиском минимального покрытия S': эта задача может быть решена за полиномиальное время. ^[10]

См. также

Ссылки

^ Терри Хэлпин (2008). Информационное моделирование и реляционные базы данных (2-е изд.). Морган Кауфманн. п. 140. ИСБН 978-0-12-373568-3 .
^ Крис Дэйт (2012). Проектирование баз данных и реляционная теория: нормальные формы и все такое . О'Рейли Медиа, Инк. с. 21. ISBN 978-1-4493-2801-6 .
^ Перейти обратно: ^а ^б ^с Авраам Зильбершац ; Генри Корт ; С. Сударшан (2010). Концепции системы баз данных (6-е изд.). МакГроу-Хилл. п. 339. ИСБН 978-0-07-352332-3 .
^ Перейти обратно: ^а ^б МОЙ Варди. Основы теории зависимости . Э. Боргер, редактор журнала «Тенденции в теоретическойИнформатика, страницы 171–224. Computer Science Press, Роквилл, Мэриленд, 1987. ISBN 0881750840
^ Абитбул, Серж ; Халл, Ричард Б .; Виану, Виктор (1995), Основы баз данных , Аддисон-Уэсли, стр. 164–168 , ISBN 0-201-53771-0
^ СК Сингх (2009) [2006]. Системы баз данных: концепции, проектирование и приложения . Пирсон Образовательная Индия. п. 323. ИСБН 978-81-7758-567-4 .
^ Эктор Гарсиа-Молина; Джеффри Д. Уллман; Дженнифер Видом (2009). Системы баз данных: полная книга (2-е изд.). Пирсон Прентис Холл. п. 73. ИСБН 978-0-13-187325-4 . Иногда это называют правилом разделения/объединения.
^ Саидиан, Х. (1 февраля 1996 г.). «Эффективный алгоритм вычисления потенциальных ключей схемы реляционной базы данных» . Компьютерный журнал . 39 (2): 124–132. дои : 10.1093/comjnl/39.2.124 . ISSN 0010-4620 .
^
Хит, Ай-Джей (1971). «Недопустимые файловые операции в реляционной базе данных». Материалы семинара ACM SIGFIDET (ныне SIGMOD) 1971 года по описанию данных, доступу и контролю - SIGFIDET '71 . стр. 19–33. дои : 10.1145/1734714.1734717 . S2CID 22069259 . цитируется в:
- Рональд Феджин и Моше Варди (1986). «Теория зависимостей данных — обзор» . В Майкле Аншеле и Уильяме Гевирце (ред.). Математика обработки информации: [краткий курс, проведенный в Луисвилле, Кентукки, 23-24 января 1984 г.] . Американское математическое соц. п. 23 . ISBN 978-0-8218-0086-7 .
- С. Дата (2005 г.). База данных в глубине: реляционная теория для практиков . О'Рейли Медиа, Инк. с. 142. ИСБН 978-0-596-10012-4 .
^ Мейер, Дэниел (1980). «Минимальные покрытия в модели реляционной базы данных» . Журнал АКМ . 27 (4): 664–674. дои : 10.1145/322217.322223 . S2CID 15789293 .

Дальнейшее чтение

Кодд, Э.Ф. (1972). «Дальнейшая нормализация реляционной модели базы данных» (PDF) . Транзакции ACM в системах баз данных . Сан-Хосе, Калифорния: Ассоциация вычислительной техники .

Внешние ссылки

Гэри Берт (лето 1999 г.). «Конспекты лекций CS 461 (Системы управления базами данных)» . Университета Мэриленда, округ Балтимор . Факультет компьютерных наук и электротехники
Джеффри Д. Уллман. «Конспекты лекций CS345» ( PostScript ) . Стэнфордский университет.
Осмар Заяне (9 июня 1998 г.). «Глава 6: Ограничения целостности» . Конспекты лекций CMPT 354 (Системы баз данных I) . Университета Саймона Фрейзера . Факультет компьютерных наук

[HalpinMorgan2008-1] Терри Хэлпин (2008). Информационное моделирование и реляционные базы данных (2-е изд.). Морган Кауфманн. п. 140. ИСБН 978-0-12-373568-3 .

[Date2012-2] Крис Дэйт (2012). Проектирование баз данных и реляционная теория: нормальные формы и все такое . О'Рейли Медиа, Инк. с. 21. ISBN 978-1-4493-2801-6 .

[SilberschatzKorth2010a-3] Перейти обратно: ^а ^б ^с Авраам Зильбершац ; Генри Корт ; С. Сударшан (2010). Концепции системы баз данных (6-е изд.). МакГроу-Хилл. п. 339. ИСБН 978-0-07-352332-3 .

[Vardi-4] Перейти обратно: ^а ^б МОЙ Варди. Основы теории зависимости . Э. Боргер, редактор журнала «Тенденции в теоретическойИнформатика, страницы 171–224. Computer Science Press, Роквилл, Мэриленд, 1987. ISBN 0881750840

[alice-5] Абитбул, Серж ; Халл, Ричард Б .; Виану, Виктор (1995), Основы баз данных , Аддисон-Уэсли, стр. 164–168 , ISBN 0-201-53771-0

[Singh2009-6] СК Сингх (2009) [2006]. Системы баз данных: концепции, проектирование и приложения . Пирсон Образовательная Индия. п. 323. ИСБН 978-81-7758-567-4 .

[Garcia-MolinaUllman2009-7] Эктор Гарсиа-Молина; Джеффри Д. Уллман; Дженнифер Видом (2009). Системы баз данных: полная книга (2-е изд.). Пирсон Прентис Холл. п. 73. ИСБН 978-0-13-187325-4 . Иногда это называют правилом разделения/объединения.

[8] Саидиан, Х. (1 февраля 1996 г.). «Эффективный алгоритм вычисления потенциальных ключей схемы реляционной базы данных» . Компьютерный журнал . 39 (2): 124–132. дои : 10.1093/comjnl/39.2.124 . ISSN 0010-4620 .

[9] Хит, Ай-Джей (1971). «Недопустимые файловые операции в реляционной базе данных». Материалы семинара ACM SIGFIDET (ныне SIGMOD) 1971 года по описанию данных, доступу и контролю - SIGFIDET '71 . стр. 19–33. дои : 10.1145/1734714.1734717 . S2CID 22069259 . цитируется в:
Рональд Феджин и Моше Варди (1986). «Теория зависимостей данных — обзор» . В Майкле Аншеле и Уильяме Гевирце (ред.). Математика обработки информации: [краткий курс, проведенный в Луисвилле, Кентукки, 23-24 января 1984 г.] . Американское математическое соц. п. 23 . ISBN 978-0-8218-0086-7 .
С. Дата (2005 г.). База данных в глубине: реляционная теория для практиков . О'Рейли Медиа, Инк. с. 142. ИСБН 978-0-596-10012-4 .

[10] Рональд Феджин и Моше Варди (1986). «Теория зависимостей данных — обзор» . В Майкле Аншеле и Уильяме Гевирце (ред.). Математика обработки информации: [краткий курс, проведенный в Луисвилле, Кентукки, 23-24 января 1984 г.] . Американское математическое соц. п. 23 . ISBN 978-0-8218-0086-7 .

[11] С. Дата (2005 г.). База данных в глубине: реляционная теория для практиков . О'Рейли Медиа, Инк. с. 142. ИСБН 978-0-596-10012-4 .

[10] Мейер, Дэниел (1980). «Минимальные покрытия в модели реляционной базы данных» . Журнал АКМ . 27 (4): 664–674. дои : 10.1145/322217.322223 . S2CID 15789293 .

[1]

[2]

[3]

[4]

[5]

[6]

[7]

[8]

[9]

[10]