Незалежність аксіоматики багатозначних залежностей в реляційних (табличних) базах даних

Abstract

UK: Актуальність. Складність розуміння концепції багатозначних залежностей (при викладенні теоретичних основ якої використовується аксіоматичний підхід) в реляційних (табличних) базах даних призводить до проблем їх моделювання, що, в свою чергу, може стати причиною порушення цілісності даних. Частковому вирішенню цих питань сприяє пошук мінімальних за кількістю та потужністю компонент аксіоматик багатозначних залежностей; звідси випливає необхідність встановлення еквівалентності розглядуваних аксіоматик та доведення незалежності їх складових. Об’єктом дослідження є аксіоматики багатозначних залежностей. Метою роботи є встановлення еквівалентності двох аксіоматик багатозначних залежностей, одна з яких є зменшеною за кількістю та потужністю компонент, та доведення незалежності останньої. Метод. При побудові доведень використовуються теоретико-множинні та логіко-алгебраїчні методи. Еквівалентність двох аксіоматик багатозначних залежностей встановлено класично: наведено відношення синтаксичного слідування і побудовано послідовності багатозначних залежностей, які є доведеннями правил кожної аксіоматики із складових іншої. Для побудови доведення незалежності аксіоматики запропоновані моделі реляційних схем, такі, що для аксіоми або правила, незалежність яких доводиться, не можна побудувати доведення з множини інших аксіом або правил. Результати. Встановлено еквівалентність аксіоматики багатозначних залежностей, запропонованої групою вчених Бірі (Beeri), Фагіним (Fagin) і Говардом (Howard) і аксіоматики багатозначних залежностей Біскупа (Biskup). Доведено незалежність останньої аксіоматики у тому розумінні, що без втрати повноти не можна опустити ні єдину аксіому, ні жодне з правил виведення. Висновки. Доведена незалежність аксіоматичної системи багатозначних залежностей Біскупа, яка має не більше за кількістю та потужністю компонент ніж інші аксіоматики багатозначних залежностей; використання саме такої аксіоматики має переваги при розробці CASE-засобів (Computer-Aided Software Engineering tools), які містять реалізацію зведення схем реляційних баз даних до четвертої нормальної форми, а також при ручному проектуванні логічної моделі реляційної бази даних. EN: Context. The complexity of understanding the concept of multivalued dependencies (when setting out their theoretical foundations, an axiomatic approach is used) in relational (table) databases leads to problems of their modeling, which in turn can cause a violation of data integrity. A partial solution to these issues is facilitated by the search for equivalent axiomatic systems of multivalued dependencies that are minimal in terms of the number and power of their components. This, in turn, requires establishing the equivalence of these axiomatic systems and proving the independence of their elements. The object of the study is the axiomatisations of multivalued dependencies.The purpose of the work is to establish the equivalence of two axiomatic systems of multivalued dependencies, one of which is minimal in terms of the number and power of components, and to prove the independence of specified axiomatics. Method. Set-theoretic and logical-algebraic methods are used in the construction of proofs. The equivalence of two axiomatic systems of multivalued dependencies is established classically: the relation of syntactic inference is considered and sequences of multivalued dependencies are constructed that are proofs of the rules of each axiomatics from the components of the other. To build proof of independence of the axiomatic system, models of relational schemes are proposed, such that for an axiom or rule whose independence is being proved, it is impossible to construct proof from set of other axioms or rules. Results. Equivalence of the axiomatisation of multivalued dependencies proposed by a group of scientists Beeri, Fagin and Howard and the Biskup’s axiomatisation of multivalued dependencies has been established. The independence of the Biskup’s axiomatic system is proved in the sense that without loss of completeness it is impossible to remove neither the only axiom nor none of the inference rules. Conclusions. The independence of the Biskup’s axiomatisation of multivalued dependencies, which has no more in number and power of components than other axiomatic systems of multivalued dependencies, is proved. Using such axiomatic system has advantages in the development of CASE-tools (Computer-Aided Software Engineering Tools), which include the implementation of reducing the relational database schema to the fourth normal form, and also, when manually designing a logical model of a relational database.