Algebraic dependencies

摘要

A new kind of data dependencies called algebraic dependencies, which generalize all previously known kinds, are proposed. A complete axiomatization of algebraic dependencies in terms of simple algebraic rewriting rules is given. In the process the expressive power of tableaux is characterized exactly, thus solving an open problem of Aho, Sagiv, and Ullman; we show that it is NP-complete to tell whether a tableau is realizable by an expression; and an interesting dual interpretation of the chase procedure is given. We also show that algebraic dependencies over a language augmented to contain union and set difference can express arbitrary domain-independent predicates of finite index over finite relations. In the class or embedded implicational dependencies recently-and independently—introduced by Fagin is shown to coincide with our algebraic dependencies. Based on this, we give a simple proof of Fagin's Armstrong relation theorem.