Что такое аксиомы Армстронга в СУБД?

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

 

Каковы аксиомы Армстронга в СУБД?

Аксиомы Армстронга, введенные Уильямом В. Армстронгом в 1974 году, представляют собой набор правил вывода, используемых для вывода всех функциональных зависимостей в реляционной базе данных. Эти правила, применяемые к набору функциональных зависимостей, обозначаемых как F+, являются одновременно надежными, гарантируя, что генерируются только зависимости внутри набора замыканий F, и полными, что означает, что применение этих правил итеративно приведет к получению всех функциональных зависимостей внутри замыкания F+.

 

Типы аксиом

Существует 3 типа аксиом:

1. Аксиома рефлексивности:
   Для набора атрибутов A и подмножества B из A, если B является подмножеством A (B⊆ A), то A → B. Эта аксиома представляет собой тривиальное свойство, в котором набор атрибутов подразумевает сам себя.
2. Аксиома расширения:
   Если A → B верно, а Y – набор атрибутов, то AY → BY также верно. Эта аксиома демонстрирует, что добавление атрибутов к зависимостям не изменяет фундаментальные зависимости. Если A → B выполняется, AC → BC выполняется для любого набора атрибутов C.
3. Аксиома транзитивности:
   Если A → B выполняется и B → C выполняется, то A → C также выполняется, аналогично переходному правилу в алгебре. Функционально это означает, что если A определяет B, а B определяет C, то A определяет C. Если X → Y и Y → Z истинны, то X → Z также истинно.

 

Правила аксиом

Ниже приведены правила использования аксиом в СУБД:

1. Декомпозиция
   Если A→ BC, то A → B и A → CДоказательство:

   A→BC (given)_______________ (i)
   BC→B (reflexivity)____________ (ii)
   A→B (transitivity from i and ii)

2. Состав
   Если A → B и C → D , то AC → BDДоказательство

   A→B_________(i)
   C→D_________(ii)
   AC→BC________(iii) (Augmentation of i and C)
   AC→B________(iv) Decomposition of iii)
   AC→AD_______(v) (Augmentation of ii and A)
   AC→D___________(vi) (Decomposition of v)
   AC→BD________ (Union iv and vi)

3. Объединение (Нотация)
   Если A → B и A → C , то A → BCДоказательство

   A→B________(i) (given)
   A→C________(ii) (given)
   A→AC_______(iii) (Augmentation of ii and A)
   AC→BC______(iv) (Augmentation of i and C)
   A→BC________(transitivity of iii and ii)

4. Псевдотранзитивность
   Если A → B и BC → D , то AC → DДоказательство

   A→B__________(i) (Given)
   BC→D________(ii) (Given)
   AC→BC_______(iii) (Augmentation of i and C)
   AC →D_________(Transitivity of iii and ii)

5. Самоопределение
   A → A для любого заданного A.Это правило напрямую следует за аксиомой рефлексивности.
6. Расширяемость
   Экстенсивность – это частный случай расширения, где C = AЕсли A→ B, то A→ AB

   В том смысле, что расширение может быть доказано с помощью экстенсивности и других аксиом, экстенсивность может заменить расширение как аксиому.

   Доказательство

   AC→A____(i)
   A→B________(ii)
   AC→B________(iii) (Transitivity of i and ii)
   AC→ABC_______(iv) (Extensivity of iii)
   ABC→BC______(v) (Reflexivity)
   AC→BC (Transitivity of iv and v)

 

Что такое отношение Армстронга в СУБД?

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

 

Почему Надежные и полные аксиомы появляются в Armstrong axioms?

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

С другой стороны, когда мы говорим, что аксиомы Армстронга полны, это означает, что многократный вывод зависимостей с использованием первичных аксиом Армстронга до тех пор, пока не будут выведены дальнейшие зависимости, приведет к полному набору всех возможных зависимостей, подразумеваемых из F. Это гарантирует, что мы вывели все соответствующие зависимости, которые могут быть выведены из данного набора функциональных зависимостей.

 

Заключение

Аксиомы Армстронга представляют собой набор правил вывода, используемых в системах управления базами данных (СУБД) для вывода всех функциональных зависимостей в реляционной базе данных. Эти аксиомы обеспечивают системный подход к получению дополнительных зависимостей на основе заданного набора функциональных зависимостей. Аксиомы являются как обоснованными, гарантирующими, что производные зависимости верны во всех допустимых состояниях отношений, так и полными, гарантирующими, что повторное применение аксиом приведет к полному набору всех подразумеваемых зависимостей.

 

Часто задаваемые вопросы, связанные с аксиомами Армстронга в СУБД

Вопрос 1. Каково значение аксиом Армстронга в СУБД?

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

Вопрос 2. Как аксиомы Армстронга применяются в СУБД?

В СУБД аксиомы Армстронга используются для вывода дополнительных функциональных зависимостей из заданного набора функциональных зависимостей. Многократно применяя аксиомы, можно систематически выводить все зависимости, которые содержатся в схеме базы данных.

Вопрос 3. Могут ли аксиомы Армстронга генерировать некорректные зависимости?

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

Вопрос 4. Ограничены ли аксиомы Армстронга определенными типами баз данных?

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

Вопрос 5. Существуют ли какие-либо ограничения на использование аксиом Армстронга?

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

Вопрос 6. Существуют ли какие-либо альтернативные методы получения функциональных зависимостей?

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