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

Концепция теории реляционных баз данных

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

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

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

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

Примеры

Автомобили

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

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

Лекции

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

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

• Идентификатор студента → Семестр.

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

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

• {Идентификатор студента, Лекция} → ТА
• {StudentID, Лекция} → {TA, Семестр}

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

Отдел по работе с персоналом

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

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

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

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

• ID отдела → Название отдела

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

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

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

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

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

${\displaystyle \vdash X\rightarrow \varnothing }$
${\displaystyle X\rightarrow Y\vdash XZ\rightarrow YZ}$
${\displaystyle 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

Закрытие

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

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

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

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

Замыканием множества атрибутов X относительно является множество X ⁺ всех атрибутов, которые функционально определяются X с помощью ⁺ . ${\displaystyle F}$ ${\displaystyle F}$

Пример

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

1. А → Б
2. Б → С
3. АБ → Д

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

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

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

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

Обложки

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

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

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

Не избыточные покрытия

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

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

Теорема Хита

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

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

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

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

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

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

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

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

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

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

Смотрите также

• Чейз (алгоритм)
• Зависимость от включения
• Присоединиться к зависимости
• Многозначная зависимость (МЗ)
• Нормализация базы данных
• Первая нормальная форма

Ссылки

1. Терри Хэлпин (2008). Информационное моделирование и реляционные базы данных (2-е изд.). Морган Кауфманн. стр. 140. ISBN 978-0-12-373568-3.
2. Крис Дейт (2012). Проектирование баз данных и реляционная теория: нормальные формы и все такое. O'Reilly Media, Inc. стр. 21. ISBN 978-1-4493-2801-6.
3. Авраам Зильбершатц ; Генри Корт ; С. Сударшан (2010). Концепции систем баз данных (6-е изд.). McGraw-Hill. стр. 339. ISBN 978-0-07-352332-3.
4. MY Vardi. Основы теории зависимости. В E. Borger, редакторе, Trends in Theoretical Computer Science, страницы 171–224. Computer Science Press, Rockville, MD, 1987. ISBN 0881750840 
5. Абитбуль, Серж ; Халл, Ричард Б.; Виану, Виктор (1995), Основы баз данных, Addison-Wesley, стр. 164–168, ISBN 0-201-53771-0
6. SK Singh (2009) [2006]. Системы баз данных: концепции, дизайн и приложения. Pearson Education India. стр. 323. ISBN 978-81-7758-567-4.
7. Гектор Гарсия-Молина; Джеффри Д. Ульман; Дженнифер Видом (2009). Системы баз данных: полная книга (2-е изд.). Pearson Prentice Hall. стр. 73. ISBN 978-0-13-187325-4.Иногда это называют правилом разделения/объединения.
8. Saiedian, H. (1996-02-01). "Эффективный алгоритм вычисления потенциальных ключей схемы реляционной базы данных". The Computer Journal . 39 (2): 124–132. doi :10.1093/comjnl/39.2.124. ISSN  0010-4620.
9. Хит, И. Дж. (1971). «Неприемлемые файловые операции в реляционной базе данных». Труды семинара ACM SIGFIDET (теперь SIGMOD) 1971 года по описанию данных, доступу и управлению — SIGFIDET '71 . С. 19–33. doi :10.1145/1734714.1734717. S2CID  22069259.цитируется в:
   • Рональд Фейгин и Моше Й. Варди (1986). "Теория зависимостей данных - Обзор". В Майкле Аншеле и Уильяме Гевиртце (ред.). Математика обработки информации: [краткий курс, проведенный в Луисвилле, Кентукки, 23-24 января 1984 г.] . Американское математическое общество. стр. 23. ISBN 978-0-8218-0086-7.
   • C. Date (2005). База данных в деталях: реляционная теория для практиков. O'Reilly Media, Inc. стр. 142. ISBN 978-0-596-10012-4.
10. Мейер, Дэниел (1980). «Минимальные покрытия в модели реляционной базы данных». Журнал ACM . 27 (4): 664–674. doi : 10.1145/322217.322223 . S2CID  15789293.

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

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

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

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