Reasoning about embedded dependencies using inclusion dependencies

2015/07/02 by Miika Hannula, Hannula, Miika
Computer Science · #03B60 #03B70 #F.4.1 #FOS: Computer and information sciences #H.2.4 #Logic in Computer Science (cs.LO) #acm:03B60 #acm:03B70 #cs.LO #msc:03B60 #msc:03B70

paper · pdf · doi:10.48550/arxiv.1507.00655

arxiv created 2015/07/02 · arxiv updated 2015/07/03

Abstract

The implication problem for the class of embedded dependencies is undecidable. However, this does not imply lackness of a proof procedure as exemplified by the chase algorithm. In this paper we present a complete axiomatization of embedded dependencies that is based on the chase and uses inclusion dependencies and implicit existential quantification in the intermediate steps of deductions.

Related

• Inclusion with repetitions and Boolean constants -- implication problems revisited
• A finite axiomatization of conditional independence and inclusion dependencies
• Axiomatizing first-order consequences in inclusion logic
• On the Interaction of Functional and Inclusion Dependencies with Independence Atoms
• Model-theoretic Characterizations of Existential Rule Languages