[{"@context":"http:\/\/schema.org\/","@type":"BlogPosting","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/armstrongs-axioms-wikipedia\/#BlogPosting","mainEntityOfPage":"https:\/\/wiki.edu.vn\/en\/wiki24\/armstrongs-axioms-wikipedia\/","headline":"Armstrong’s axioms – Wikipedia","name":"Armstrong’s axioms – Wikipedia","description":"From Wikipedia, the free encyclopedia Armstrong’s axioms are a set of references (or, more precisely, inference rules) used to infer","datePublished":"2021-10-17","dateModified":"2021-10-17","author":{"@type":"Person","@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/#Person","name":"lordneo","url":"https:\/\/wiki.edu.vn\/en\/wiki24\/author\/lordneo\/","image":{"@type":"ImageObject","@id":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","url":"https:\/\/secure.gravatar.com\/avatar\/c9645c498c9701c88b89b8537773dd7c?s=96&d=mm&r=g","height":96,"width":96}},"publisher":{"@type":"Organization","name":"Enzyklop\u00e4die","logo":{"@type":"ImageObject","@id":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","url":"https:\/\/wiki.edu.vn\/wiki4\/wp-content\/uploads\/2023\/08\/download.jpg","width":600,"height":60}},"image":{"@type":"ImageObject","@id":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/d6f68fc8927704e56f96b49d2eade3ce4586506c","url":"https:\/\/wikimedia.org\/api\/rest_v1\/media\/math\/render\/svg\/d6f68fc8927704e56f96b49d2eade3ce4586506c","height":"","width":""},"url":"https:\/\/wiki.edu.vn\/en\/wiki24\/armstrongs-axioms-wikipedia\/","wordCount":10079,"articleBody":"From Wikipedia, the free encyclopediaArmstrong’s axioms are a set of references (or, more precisely, inference rules) used to infer all the functional dependencies on a relational database. They were developed by William W. Armstrong in his 1974 paper.[1] The axioms are sound in generating only functional dependencies in the closure of a set of functional dependencies (denoted as  F+{displaystyle F^{+}}) when applied to that set (denoted as F{displaystyle F}). They are also complete in that repeated application of these rules will generate all functional dependencies in the closure F+{displaystyle F^{+}}.More formally, let \u27e8R(U),F\u27e9{displaystyle langle R(U),Frangle } denote a relational scheme over the set of attributes U{displaystyle U} with a set of functional dependencies F{displaystyle F}. We say that a functional dependency f{displaystyle f} is logically implied by F{displaystyle F}, and denote it with F\u22a8f{displaystyle Fmodels f} if and only if for every instance r{displaystyle r} of R{displaystyle R} that satisfies the functional dependencies in F{displaystyle F}, r{displaystyle r} also satisfies f{displaystyle f}. We denote by F+{displaystyle F^{+}} the set of all functional dependencies that are logically implied by F{displaystyle F}.Furthermore, with respect to a set of inference rules A{displaystyle A}, we say that a functional dependency f{displaystyle f} is derivable from the functional dependencies in F{displaystyle F} by the set of inference rules A{displaystyle A}, and we denote it by F\u22a2Af{displaystyle Fvdash _{A}f} if and only if f{displaystyle f} is obtainable by means of repeatedly applying the inference rules in A{displaystyle A} to functional dependencies in F{displaystyle F}. We denote by FA\u2217{displaystyle F_{A}^{*}} the set of all functional dependencies that are derivable from F{displaystyle F} by inference rules in A{displaystyle A}.Then, a set of inference rules A{displaystyle A} is sound if and only if the following holds:FA\u2217\u2286F+{displaystyle F_{A}^{*}subseteq F^{+}}that is to say, we cannot derive by means of A{displaystyle A} functional dependencies that are not logically implied by F{displaystyle F}.The set of inference rules A{displaystyle A} is said to be complete if the following holds:F+\u2286FA\u2217{displaystyle F^{+}subseteq F_{A}^{*}}more simply put, we are able to derive by A{displaystyle A} all the functional dependencies that are logically implied by F{displaystyle F}.Table of ContentsAxioms (primary rules)[edit]Axiom of reflexivity[edit]Axiom of augmentation[edit]Axiom of transitivity[edit]Additional rules (Secondary Rules)[edit]Decomposition[edit]Proof[edit]Composition[edit]Proof[edit]Union (Notation)[edit]Proof[edit]Pseudo transitivity[edit]Proof[edit]Self determination[edit]Extensivity[edit]Proof[edit]Armstrong relation[edit]References[edit]External links[edit]Axioms (primary rules)[edit]Let R(U){displaystyle R(U)} be a relation scheme over the set of attributes U{displaystyle U}. Henceforth we will denote by letters X{displaystyle X}, Y{displaystyle Y}, Z{displaystyle Z} any subset of U{displaystyle U} and, for short, the union of two sets of attributes X{displaystyle X} and Y{displaystyle Y} by XY{displaystyle XY} instead of the usual X\u222aY{displaystyle Xcup Y}; this notation is rather standard in database theory when dealing with sets of attributes.Axiom of reflexivity[edit]If X{displaystyle X} is a set of attributes and Y{displaystyle Y} is a subset of X{displaystyle X}, then X{displaystyle X} holds Y{displaystyle Y}. Hereby, X{displaystyle X} holds Y{displaystyle Y} [X\u2192Y{displaystyle Xto Y}] means that X{displaystyle X} functionally determines Y{displaystyle Y}.If Y\u2286X{displaystyle Ysubseteq X} then X\u2192Y{displaystyle Xto Y}.Axiom of augmentation[edit]If X{displaystyle X} holds Y{displaystyle Y} and Z{displaystyle Z} is a set of attributes, then XZ{displaystyle XZ} holds YZ{displaystyle YZ}. It means that attribute in dependencies does not change the basic dependencies.If X\u2192Y{displaystyle Xto Y}, then XZ\u2192YZ{displaystyle XZto YZ} for any Z{displaystyle Z}.Axiom of transitivity[edit]If X{displaystyle X} holds Y{displaystyle Y} and Y{displaystyle Y} holds Z{displaystyle Z}, then X{displaystyle X} holds Z{displaystyle Z}.If X\u2192Y{displaystyle Xto Y} and Y\u2192Z{displaystyle Yto Z}, then X\u2192Z{displaystyle Xto Z}.Additional rules (Secondary Rules)[edit]These rules can be derived from the above axioms.Decomposition[edit]If X\u2192YZ{displaystyle Xto YZ} then X\u2192Y{displaystyle Xto Y} and X\u2192Z{displaystyle Xto Z}.Proof[edit]1. X\u2192YZ{displaystyle Xto YZ}(Given)2. YZ\u2192Y{displaystyle YZto Y}(Reflexivity)3. X\u2192Y{displaystyle Xto Y}(Transitivity of 1 & 2)Composition[edit]If X\u2192Y{displaystyle Xto Y} and A\u2192B{displaystyle Ato B} then XA\u2192YB{displaystyle XAto YB}.Proof[edit]Union (Notation)[edit]If X\u2192Y{displaystyle Xto Y} and X\u2192Z{displaystyle Xto Z} then X\u2192YZ{displaystyle Xto YZ}.Proof[edit]Pseudo transitivity[edit]If X\u2192Y{displaystyle Xto Y} and YZ\u2192W{displaystyle YZto W} then XZ\u2192W{displaystyle XZto W}.Proof[edit]1. X\u2192Y{displaystyle Xto Y}(Given)2. YZ\u2192W{displaystyle YZto W}(Given)3. XZ\u2192YZ{displaystyle XZto YZ}(Augmentation of 1 & Z)4. XZ\u2192W{displaystyle XZto W}(Transitivity of 3 and 2)Self determination[edit]I\u2192I{displaystyle Ito I} for any I{displaystyle I}. This follows directly from the axiom of reflexivity.Extensivity[edit]The following property is a special case of augmentation when Z=X{displaystyle Z=X}.If X\u2192Y{displaystyle Xto Y}, then X\u2192XY{displaystyle Xto XY}.Extensivity can replace augmentation as axiom in the sense that augmentation can be proved from extensivity together with the other axioms.Proof[edit]Armstrong relation[edit]Given a set of functional dependencies F{displaystyle F}, an Armstrong relation is a relation which satisfies all the functional dependencies in the closure F+{displaystyle F^{+}} and only those dependencies. Unfortunately, the minimum-size Armstrong relation for a given set of dependencies can have a size which is an exponential function of the number of attributes in the dependencies considered.[2]References[edit]External links[edit]  "},{"@context":"http:\/\/schema.org\/","@type":"BreadcrumbList","itemListElement":[{"@type":"ListItem","position":1,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/#breadcrumbitem","name":"Enzyklop\u00e4die"}},{"@type":"ListItem","position":2,"item":{"@id":"https:\/\/wiki.edu.vn\/en\/wiki24\/armstrongs-axioms-wikipedia\/#breadcrumbitem","name":"Armstrong’s axioms – Wikipedia"}}]}]