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

В теории реляционных баз данных функциональная зависимость — это следующее ограничение между двумя наборами атрибутов в отношении : При наличии отношения 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)\бабочка \Pi _{XZ}(R)=R}

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

Примеры

Автомобили

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

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

Лекции

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

Студенческий билетСеместрЛекцияТА
12346Численные методыДжон
12214Численные методыСмит
12346Визуальные вычисленияБоб
12012Численные методыПитер
12012Физика 2Саймон

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

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

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

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

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

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

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

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

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

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

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

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

  • 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} R {\displaystyle R} F {\displaystyle F} R {\displaystyle R} F {\displaystyle F} F {\displaystyle F}

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

Замыканием множества атрибутов X относительно является множество X + всех атрибутов, которые функционально определяются X с помощью + . F {\displaystyle F} 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 в может быть выведен из . охватывает , если + ⊆ + Каждый набор функциональных зависимостей имеет каноническое покрытие . F {\displaystyle F} G {\displaystyle G} G {\displaystyle G} F {\displaystyle F} F {\displaystyle F} G {\displaystyle G} G {\displaystyle G} F {\displaystyle F}

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

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

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

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

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

Теорема Хита

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

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

Однако функциональные зависимости не следует путать с зависимостями включения , которые являются формализмом для внешних ключей; даже если они используются для нормализации, функциональные зависимости выражают ограничения по одному отношению (схеме), тогда как зависимости включения выражают ограничения между схемами отношений в схеме базы данных . Более того, эти два понятия даже не пересекаются в классификации зависимостей: функциональные зависимости являются зависимостями, порождающими равенство , тогда как зависимости включения являются зависимостями, порождающими кортежи . Обеспечение ссылочных ограничений после декомпозиции схемы отношений (нормализации) требует нового формализма, т. е. зависимостей включения. В декомпозиции, полученной в результате теоремы Хита, нет ничего, что мешало бы вставке кортежей при наличии некоторого значения X, не найденного в . Π X Z ( R ) {\displaystyle \Pi _{XZ}(R)} Π X Y ( 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. ^ abc Авраам Зильбершатц ; Генри Корт ; С. Сударшан (2010). Концепции систем баз данных (6-е изд.). McGraw-Hill. стр. 339. ISBN 978-0-07-352332-3.
  4. ^ ab 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.Значок закрытого доступа

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

  • Гари Берт (лето 1999 г.). «Конспект лекций по CS 461 (Системы управления базами данных)». Университет Мэриленда, округ Балтимор, кафедра компьютерных наук и электротехники.
  • Джеффри Д. Ульман. "CS345 Lecture Notes" ( PostScript ) . Стэнфордский университет.
  • Osmar Zaiane (9 июня 1998 г.). "Глава 6: Ограничения целостности". CMPT 354 (Системы баз данных I) лекции . Кафедра вычислительной техники Университета Саймона Фрейзера .
Retrieved from "https://en.wikipedia.org/w/index.php?title=Functional_dependency&oldid=1255139264"