Reasoning about embedded dependencies using inclusion dependencies

DOI10.1007/978-3-662-48899-7_2MaRDI QIDQ3460037zbMATH OpenOpenAlexFDO

Authors Miika Hannula

Publication date 12 January 2016

Published in Logic for Programming, Artificial Intelligence, and Reasoning (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1507.00655

zbMATH Keywords

axiomatizationchasedependence logicembedded dependencyequality-generating dependencyimplication probleminclusion dependencytuple-generating dependency

Mathematics Subject Classification ID

Logic in computer science (03B70) Database theory (68P15)

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.

Recommendations

• On the undecidability of implications between embedded multivalued database dependencies
• The implication problem for functional and inclusion dependencies
• A Proof Procedure for Data Dependencies
• scientific article; zbMATH DE number 4112078
• The Implication Problem for Functional and Inclusion Dependencies is Undecidable

Cited in

(9)

• A logical approach to context-specific independence
• On the undecidability of implications between embedded multivalued database dependencies
• A finite axiomatization of conditional independence and inclusion dependencies
• A Logical Approach to Context-Specific Independence
• The inference problem for template dependencies
• The Implication Problem for Functional and Inclusion Dependencies is Undecidable
• Technical Correspondence
• A sound and complete axiomatization of embedded cross dependencies
• Corrigendum to ``On the undecidability of implications between embedded multivalued database dependencies

This page was built for publication: Reasoning about embedded dependencies using inclusion dependencies

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q3460037)