The expanded implication problem of data dependencies

Abstract

The implication problem is the problem of deciding whether a given set of dependencies implies or entails another dependency. Up to now, the entailment of excluded dependencies or independencies is only regarded on a metalogical level which is not suitable for an automatic inference process of these. But the inference of independencies are important for new topics in database research like semantic query optimization. In this paper, the expanded implication problem is discussed in order to decide implications of dependencies and independencies. The main result is an axiomatization of functional, inclusion and multivalued independencies and the corresponding inference relations. Also we discuss the use of independencies in knowledge discovery in databases and semantic query optimization.