В теории реляционных баз данных функциональная зависимость - это ограничение между двумя наборами атрибутов в отношении из базы данных. Другими словами, функциональная зависимость - это ограничение между двумя ключами. Учитывая отношение R и наборы атрибутов, X, как говорят, функционально определяет Y (пишется X → Y ) тогда и только тогда, когда каждое значение X в R связано ровно с одним значением Y в R ; R затем называется удовлетворить функциональную зависимость X → Y . Эквивалентно проекция является функцией , то есть Y является функцией X . [1] [2] Говоря простыми словами, если значения для X атрибутов известны (говорят , что они х ), то значения для Y атрибуты , соответствующие х можно определить, посмотрев их в любой кортеж из R , содержащий х . Обычно X называется детерминантным множеством, а Y - зависимым множеством. Функциональная зависимость FD: X → Y называется тривиальным , если Y представляет собой подмножество из X .
Другими словами, зависимость FD: X → Y означает , что значения Y определяются значениями X . Два кортежей разделяющих один и то же значение X обязательно будут иметь одинаковые значения Y .
Определение функциональных зависимостей является важной частью проектирования баз данных в реляционной модели , а также при нормализации и денормализации базы данных . Простое применение функциональных зависимостей - это теорема Хита ; в нем говорится, что отношение R над набором атрибутов U и удовлетворяющее функциональной зависимости X → Y можно безопасно разделить на два отношения, обладающие свойством декомпозиции соединения без потерь , а именно нагде Z = U - XY - остальные атрибуты. ( Объединения наборов атрибутов обычно обозначаются простыми сопоставлениями в теории баз данных.) Важным понятием в этом контексте является ключ-кандидат , определенный как минимальный набор атрибутов, который функционально определяет все атрибуты в отношении. Функциональные зависимости, наряду с доменами атрибутов , выбираются таким образом, чтобы сгенерировать ограничения, которые исключили бы из системы как можно больше данных, не соответствующих домену пользователя .
Понятие логической импликации определяется для функциональных зависимостей следующим образом: набор функциональных зависимостей логически подразумевает другой набор зависимостей , если какое-либо отношение R, удовлетворяющее всем зависимостям от также удовлетворяет всем зависимостям от ; это обычно пишется. Понятие логической импликации функциональных зависимостей допускает здравую и полную конечную аксиоматизацию , известную как аксиомы Армстронга .
Примеры
Легковые автомобили
Предположим, кто-то разрабатывает систему для отслеживания транспортных средств и мощности их двигателей. У каждого автомобиля есть уникальный идентификационный номер автомобиля (VIN). Можно было бы написать VIN → EngineCapacity, потому что для двигателя транспортного средства было бы неприемлемо иметь более одной мощности. (Предполагая, что в этом случае у транспортных средств только один двигатель.) С другой стороны, EngineCapacity → VIN неверен, потому что может быть много автомобилей с одинаковым объемом двигателя.
Эта функциональная зависимость может предполагать, что атрибут EngineCapacity должен быть связан с VIN ключа кандидата . Однако это не всегда может быть уместным. Например, если эта функциональная зависимость возникает в результате транзитивных функциональных зависимостей VIN → VehicleModel и VehicleModel → EngineCapacity, то это не приведет к нормализованному отношению.
Лекции
Этот пример иллюстрирует концепцию функциональной зависимости. Смоделирована ситуация, когда студенты колледжа посещают одну или несколько лекций, на каждой из которых им назначается ассистент преподавателя (TA). Далее предположим, что каждый студент находится в каком-то семестре и идентифицируется уникальным целочисленным идентификатором.
Студенческий билет | Семестр | Лекция | TA |
---|---|---|---|
1234 | 6 | Численные методы | Джон |
1221 | 4 | Численные методы | Смит |
1234 | 6 | Визуальные вычисления | Боб |
1201 | 2 | Численные методы | Питер |
1201 | 2 | Физика II | Саймон |
Мы замечаем, что всякий раз, когда две строки в этой таблице имеют одинаковый идентификатор StudentID, они также обязательно имеют одинаковые значения Semester. Этот основной факт может быть выражен функциональной зависимостью:
- StudentID → Семестр.
Обратите внимание, что если бы была добавлена строка, в которой у студента было другое значение семестра, функциональная зависимость FD больше не существовала бы. Это означает, что данные подразумевают FD, поскольку могут иметь значения, которые сделали бы FD недействительным.
Можно выделить другие нетривиальные функциональные зависимости, например:
- {StudentID, Lecture} → TA
- {StudentID, Lecture} → {TA, Semester}
Последнее выражает тот факт, что набор {StudentID, Lecture} является суперключом отношения.
Модель отдела сотрудников
Классическим примером функциональной зависимости является модель отдела сотрудников.
ID сотрудника | Имя сотрудника | ID отдела | Название отдела |
---|---|---|---|
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
«Рефлексивность» можно ослабить до , то есть это фактическая аксиома , где два других являются собственными правилами вывода , точнее порождающими следующие правила синтаксического следствия: [4]
.
Эти три правила представляют собой здравую и полную аксиоматизацию функциональных зависимостей. Эта аксиоматизация иногда описывается как конечная, потому что количество правил вывода конечно, [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
Закрытие функциональной зависимости
Замыкание - это, по сути, полный набор значений, который может быть определен из набора известных значений для данного отношения с использованием его функциональных зависимостей. Для доказательства используются аксиомы Армстронга, т. Е. Рефлексивность, увеличение, транзитивность.
Дано а также набор FD, который удерживается в : Закрытие в (обозначается + ) - это множество всех ФД, которые логически вытекают из.
Замыкание набора атрибутов
Замыкание набора атрибутов X относительно - это набор X + всех атрибутов, которые функционально определяются X с помощью+ .
Пример
Представьте себе следующий список ФД. Мы собираемся вычислить замыкание для A из этого отношения.
1. A → B
2. B → C 3. AB → D
Закрытие будет следующим:
a) A → A (согласно рефлексивности Армстронга)
b) A → AB (согласно 1. и (a))
c) A → ABD (согласно (b), 3 и транзитивности Армстронга)
d) A → ABCD (согласно (c ), и 2)
Замыкание, следовательно, A → ABCD. Вычислив закрытие A, мы подтвердили, что A также является хорошим кандидатом ключа, поскольку его закрытие - это каждое отдельное значение данных в отношении.
Обложки и эквивалентность
Охватывает
Определение : охватывает если каждый ФД в можно сделать вывод из . охватывает если + ⊆+
Каждый набор функциональных зависимостей имеет каноническую оболочку .
Эквивалентность двух наборов ФД
Два комплекта FD а также по схеме эквивалентны, написаны ≡ , если + =+ . Если ≡ , тогда это прикрытие для и наоборот. Другими словами, эквивалентные наборы функциональных зависимостей называются покрытиями друг друга.
Не дублирующие крышки
Множество FD не является избыточным, если нет подходящего подмножества из с участием ≡ . Если такой существуют, является избыточным. это неизбыточное покрытие для если это прикрытие для а также не является избыточным.
Альтернативная характеристика неизбыточности состоит в том, чтоявляется неизбыточны , если нет FD X → Y в такой, что - { X → Y } Х → Y . Вызов FD X → Y в избыточный в если - { X → Y } Х → Y .
Приложения к нормализации
Теорема Хита
Важное свойство (приводящее к немедленному применению) функциональных зависимостей состоит в том, что если R является отношением со столбцами, названными из некоторого набора атрибутов U и R удовлетворяет некоторой функциональной зависимости X → Y, тогде Z = U - XY . Интуитивно, если функциональная зависимость X → Y выполняется в R , то отношение можно безопасно разделить на два отношения рядом со столбцом X (который является ключом для), гарантируя, что при обратном соединении двух частей данные не будут потеряны, т. е. функциональная зависимость обеспечивает простой способ построения декомпозиции соединения R без потерь в двух меньших отношениях. Этот факт иногда называют теоремой Хитса ; это один из первых результатов теории баз данных. [8]
Теорема Хита фактически говорит, что мы можем извлечь значения Y из большого отношения R и сохранить их в одном,, который не имеет повторений значений в строке для X и фактически является таблицей поиска для Y с ключом X и, следовательно, имеет только одно место для обновления Y, соответствующего каждому X, в отличие от «большого» отношения R, где существует потенциально много копий каждый X , каждый со своей копией Y, которые необходимо синхронизировать при обновлениях. (Это устранение избыточности является преимуществом в контекстах OLTP , где ожидается много изменений, но не так много в контекстах OLAP , которые в основном связаны с запросами.) Декомпозиция Хита оставляет только X в качестве внешнего ключа в оставшейся части большой таблицы..
Однако функциональные зависимости не следует путать с зависимостями включения , которые являются формализмом для внешних ключей; Несмотря на то, что они используются для нормализации, функциональные зависимости выражают ограничения по одному отношению (схеме), тогда как зависимости включения выражают ограничения между схемами отношений в схеме базы данных . Более того, эти два понятия даже не пересекаются при классификации зависимостей : функциональные зависимости - это зависимости, порождающие равенство, тогда как зависимости включения - это зависимости, порождающие кортежи . Применение ссылочных ограничений после декомпозиции схемы отношений (нормализации) требует нового формализма, то есть зависимостей включения. В разложении, полученном в результате теоремы Хита, нет ничего, препятствующего вставке кортежей вимеющий какое-то значение X, не найденное в.
Нормальные формы
Нормальные формы - это уровни нормализации базы данных, которые определяют «качество» таблицы. Обычно третья нормальная форма считается «хорошим» стандартом для реляционной базы данных. [ необходима цитата ]
Нормализация направлена на освобождение базы данных от аномалий обновления, вставки и удаления. Это также гарантирует, что когда новое значение вводится в отношение, оно оказывает минимальное влияние на базу данных и, следовательно, минимальное влияние на приложения, использующие базу данных. [ необходима цитата ]
Неприводимая функция в зависимости от набора
Набор функциональных зависимостей S является неприводимым, если он обладает следующими тремя свойствами:
- Каждый правый набор функциональной зависимости S содержит только один атрибут.
- Каждый левый набор функциональной зависимости S неприводим. Это означает, что уменьшение любого атрибута из левого набора изменит содержимое S (S потеряет некоторую информацию).
- Уменьшение любой функциональной зависимости изменит содержимое S.
Наборы функциональных зависимостей с этими свойствами также называют каноническими или минимальными . Нахождение такого набора S функциональных зависимостей, который эквивалентен некоторому входному набору S ', предоставленному в качестве входных данных, называется поиском минимального покрытия S': эта проблема может быть решена за полиномиальное время. [9]
Смотрите также
- Чейз (алгоритм)
- Зависимость включения
- Присоединиться к зависимости
- Многозначная зависимость (MVD)
- Нормализация базы данных
- Первая нормальная форма
Рекомендации
- ^ Терри Halpin (2008). Информационное моделирование и реляционные базы данных (2-е изд.). Морган Кауфманн. п. 140. ISBN 978-0-12-373568-3.
- ^ Крис Дэйт (2012). Дизайн баз данных и теория отношений: нормальные формы и все такое . O'Reilly Media, Inc. стр. 21. ISBN 978-1-4493-2801-6.
- ^ а б в Авраам Зильбершатц; Генри Корт; С. Сударшан (2010). Концепции системы баз данных (6-е изд.). Макгроу-Хилл. п. 339. ISBN. 978-0-07-352332-3.
- ^ а б М. Ю. Варди. Основы теории зависимости . В Э. Боргер, редактор, Тенденции теоретической информатики, страницы 171–224. Издательство компьютерных наук, Роквилл, Мэриленд, 1987. ISBN 0881750840
- ^ Абитебул, Серж ; Халл, Ричард Б .; Виану, Виктор (1995), Основы баз данных , Addison-Wesley, стр. 164–168 , ISBN 0-201-53771-0
- ^ С. К. Сингх (2009) [2006]. Системы баз данных: концепции, дизайн и приложения . Pearson Education India. п. 323. ISBN 978-81-7758-567-4.
- ^ Эктор Гарсиа-Молина; Джеффри Д. Уллман; Дженнифер Видом (2009). Системы баз данных: полная книга (2-е изд.). Пирсон Прентис Холл. п. 73. ISBN 978-0-13-187325-4. Иногда это называют правилом разделения / объединения.
- ^ Хит, Эй Джей (1971). «Недопустимые файловые операции в реляционной базе данных». Материалы семинара 1971 года ACM SIGFIDET (ныне SIGMOD) по описанию данных, доступу и управлению - SIGFIDET '71 . С. 19–33. DOI : 10.1145 / 1734714.1734717 . цитируется в:
- Рональд Феджин и Моше Ю. Варди (1986). «Теория зависимостей данных - обзор». В Майкле Аншеле и Уильяме Гевиртце (ред.). Математика обработки информации: [краткий курс, проведенный в Луисвилле, Кентукки, 23-24 января 1984 г.] . American Mathematical Soc. п. 23 . ISBN 978-0-8218-0086-7.
- C. Дата (2005). База данных в глубине: реляционная теория для практиков . O'Reilly Media, Inc. стр. 142. ISBN. 978-0-596-10012-4.
- ^ Мейер, Даниэль (1980). «Минимальные покрытия в модели реляционной базы данных». Журнал ACM . DOI : 10.1145 / 322217.322223 .
Внешние ссылки
- Гэри Берт (лето 1999 г.). «Конспект лекции CS 461 (Системы управления базами данных)» . Университет Мэриленда, факультет информатики и электротехники округа Балтимор .
- Джеффри Д. Ульман. «Лекционные заметки CS345» ( PostScript ) . Стэндфордский Университет.
- Осмар Зайане (9 июня 1998 г.). «Глава 6: Ограничения целостности» . Конспект лекций CMPT 354 (Системы баз данных I) . Факультет компьютерных наук Университета Саймона Фрейзера .