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

В реляционных баз данных теории функциональная зависимость — это ограничение между двумя наборами атрибутов в отношении базы данных. Другими словами, функциональная зависимость — это ограничение между двумя атрибутами в отношении. Учитывая отношение R и наборы атрибутов $X,Y\subseteq R$ , что X Говорят функционально определяет Y (записывается X → Y ) тогда и только тогда, когда каждое значение X в R связано ровно с одним значением Y в R ; удовлетворяет Тогда говорят, что функциональной зависимости X → Y. R Эквивалентно, проекция $\Pi _{X,Y}R$ является функцией , т.е. является функцией от X. Y ^[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), Основы баз данных , Аддисон-Уэсли, стр. 107–114. стр. 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), Основы баз данных , Аддисон-Уэсли, стр. 107–114. стр. 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]