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

Введение

Концепция теории реляционных баз данных – это концепция в теории реляционных баз данных.

В теории реляционных баз данных функциональная зависимость – это ограничение между двумя множествами атрибутов в отношении из базы данных. Иными словами, функциональная зависимость – это ограничение между двумя атрибутами в отношении. Для отношения R и множеств атрибутов, X функционально определяет Y (обозначается X → Y) тогда и только тогда, когда каждое значение X в R связано ровно с одним значением Y в R; тогда говорят, что R удовлетворяет функциональной зависимости X → Y. Эквивалентно, проекция является функцией, то есть Y является функцией от X. Проще говоря, если известны значения атрибутов X (например, они равны x), то значения атрибутов Y, соответствующие x, можно определить, найдя их в любой кортеже R, содержащем x. Обычно X называют детерминирующим множеством, а Y – зависимым множеством. Функциональная зависимость FD: X → Y называется тривиальной, если Y является подмножеством X. Другими словами, зависимость FD: X → Y означает, что значения Y определяются значениями X. Две кортежа, имеющие одинаковые значения X, обязательно будут иметь одинаковые значения Y. Определение функциональных зависимостей является важной частью проектирования баз данных в реляционной модели, а также нормализации и денормализации баз данных. Простым применением функциональных зависимостей является теорема Хита; она утверждает, что отношение R над множеством атрибутов U, удовлетворяющее функциональной зависимости X → Y, можно безопасно разбить на два отношения, обладающих свойством без потерь при объединении, а именно на , где Z = U − XY – остальные атрибуты. (Объединения множеств атрибутов обычно обозначаются их последовательным перечислением в теории баз данных.) Важным понятием в этом контексте является кандидатный ключ, определяемый как минимальное множество атрибутов, которое функционально определяет все атрибуты в отношении. Функциональные зависимости, наряду с доменами атрибутов, выбираются таким образом, чтобы генерировать ограничения, исключающие из системы как можно больше данных, не соответствующих предметной области пользователя. Понятие логического следования определяется для функциональных зависимостей следующим образом: множество функциональных зависимостей логически влечет другой набор зависимостей, если любое отношение R, удовлетворяющее всем зависимостям из , также удовлетворяет всем зависимостям из ; это обычно записывается как . Понятие логического следования для функциональных зависимостей имеет звучную и полную конечную аксиоматизацию, известную как аксиомы Армстронга.

In relational database theory, a functional dependency is a constraint between two sets of attributes in a relation from a database. In other words, a functional dependency is a constraint between two attributes in a relation. Given a relation R and sets of attributes , X is said to functionally determine Y (written X → Y) if and only if each X value in R is associated with precisely one Y value in R; R is then said to satisfy the functional dependency X → Y. Equivalently, the projection is a function, i. e. Y is a function of X. In simple words, if the values for the X attributes are known (say they are x), then the values for the Y attributes corresponding to x can be determined by looking them up in any tuple of R containing x. Customarily X is called the determinant set and Y the dependent set. A functional dependency FD: X → Y is called trivial if Y is a subset of X. In other words, a dependency FD: X → Y means that the values of Y are determined by the values of X. Two tuples sharing the same values of X will necessarily have the same values of Y. The determination of functional dependencies is an important part of designing databases in the relational model, and in database normalization and denormalization. A simple application of functional dependencies is Heath's theorem; it says that a relation R over an attribute set U and satisfying a functional dependency X → Y can be safely split in two relations having the lossless join decomposition property, namely into where Z = U − XY are the rest of the attributes. (Unions of attribute sets are customarily denoted by there juxtapositions in database theory.) An important notion in this context is a candidate key, defined as a minimal set of attributes that functionally determine all of the attributes in a relation. The functional dependencies, along with the attribute domains, are selected so as to generate constraints that would exclude as much data inappropriate to the user domain from the system as possible. A notion of logical implication is defined for functional dependencies in the following way: a set of functional dependencies logically implies another set of dependencies , if any relation R satisfying all dependencies from also satisfies all dependencies from ; this is usually written The notion of logical implication for functional dependencies admits a sound and complete finite axiomatization, known as Armstrong's axioms.

Автомобили

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

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

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

Обложки

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

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

Два набора функциональных зависимостей и над схемой эквивалентны, что записывается как ≡, если + = +. Если ≡, то один набор является покрытием для другого и наоборот. Иными словами, эквивалентные наборы функциональных зависимостей называются покрытиями друг друга.

Теорема Хита

Важным свойством (дающим непосредственное применение) функциональных зависимостей является то, что если R – это отношение с колонками, названными из некоторого набора атрибутов U, и R удовлетворяет некоторой функциональной зависимости X → Y, то, где Z = U − XY. Интуитивно, если функциональная зависимость X → Y выполняется в R, то отношение можно безопасно разделить на два отношения вместе с колонкой X (которая является ключом для ), гарантируя, что при соединении двух частей обратно не будет потеряно никаких данных, то есть функциональная зависимость предоставляет простой способ построения декомпозиции R без потерь при соединении на два меньших отношения. Этот факт иногда называют теоремой Хитса; это один из ранних результатов в теории баз данных. Теорема Хитса, по сути, говорит о том, что мы можем извлечь значения Y из большого отношения R и сохранить их в отдельное отношение , которое не содержит повторений значений Y для каждого X и фактически является таблицей поиска для Y, индексированной по X, и, следовательно, имеет только одно место для обновления Y, соответствующего каждому X, в отличие от "большого" отношения R, где потенциально существует множество копий каждого X, каждая из которых имеет свою копию Y, которую необходимо синхронизировать при обновлениях. (Это устранение избыточности является преимуществом в контексте OLTP, где ожидается много изменений, но менее важно в контексте OLAP, который в основном включает в себя запросы.) Декомпозиция Хитса оставляет только X для использования в качестве внешнего ключа в оставшейся части большого отношения.

An important property (yielding an immediate application) of functional dependencies is that if R is a relation with columns named from some set of attributes U and R satisfies some functional dependency X → Y then where Z = U − XY. Intuitively, if a functional dependency X → Y holds in R, then the relation can be safely split in two relations alongside the column X (which is a key for ) ensuring that when the two parts are joined back no data is lost, i. e. a functional dependency provides a simple way to construct a lossless join decomposition of R in two smaller relations. This fact is sometimes called Heaths theorem; it is one of the early results in database theory. Heath's theorem effectively says we can pull out the values of Y from the big relation R and store them into one, , which has no value repetitions in the row for X and is effectively a lookup table for Y keyed by X and consequently has only one place to update the Y corresponding to each X unlike the "big" relation R where there are potentially many copies of each X, each one with its copy of Y which need to be kept synchronized on updates. (This elimination of redundancy is an advantage in OLTP contexts, where many changes are expected, but not so much in OLAP contexts, which involve mostly queries.) Heath's decomposition leaves only X to act as a foreign key in the remainder of the big table
Functional dependencies however should not be confused with inclusion dependencies, which are the formalism for foreign keys; even though they are used for normalization, functional dependencies express constraints over one relation (schema), whereas inclusion dependencies express constraints between relation schemas in a database schema. Furthermore, the two notions do not even intersect in the classification of dependencies: functional dependencies are equality generating dependencies whereas inclusion dependencies are tuple generating dependencies. Enforcing referential constraints after relation schema decomposition (normalization) requires a new formalism, i. e. inclusion dependencies. In the decomposition resulting from Heath's theorem, there is nothing preventing the insertion of tuples in having some value of X not found in .

Однако функциональные зависимости не следует путать с зависимостями включения, которые являются формализмом для внешних ключей; хотя они и используются для нормализации, функциональные зависимости выражают ограничения внутри одного отношения (схемы), в то время как зависимости включения выражают ограничения между схемами отношений в схеме базы данных. Более того, эти два понятия даже не пересекаются в классификации зависимостей: функциональные зависимости являются зависимостями, генерирующими равенства, а зависимости включения – зависимостями, генерирующими кортежи. Обеспечение ссылочной целостности после декомпозиции схемы отношений (нормализации) требует нового формализма, то есть зависимостей включения. В декомпозиции, полученной в результате теоремы Хитса, ничто не препятствует вставке кортежей в , содержащих значения X, отсутствующие в .

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

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