Inclusion dependencies and their interaction with functional dependencies in SQL
作者：
Highlights：
• Simple inclusion dependencies and NOT NULL constraints are not finitely axiomatizable.
• The new class of not null inclusion dependencies (NNINDs) subsumes simple and partial inclusion dependencies.
• The implication problem for NNINDs is finitely axiomatizable, PSPACE-complete, and fixed parameter-tractable in their arity.
• Typed acyclic NNINDs are NP-complete, and tree-like NNINDs are linear time decidable.
• Super-reducedness is an efficient condition sufficient to guarantee no interaction between functional dependencies and NNINDs.
摘要
•Simple inclusion dependencies and NOT NULL constraints are not finitely axiomatizable.•The new class of not null inclusion dependencies (NNINDs) subsumes simple and partial inclusion dependencies.•The implication problem for NNINDs is finitely axiomatizable, PSPACE-complete, and fixed parameter-tractable in their arity.•Typed acyclic NNINDs are NP-complete, and tree-like NNINDs are linear time decidable.•Super-reducedness is an efficient condition sufficient to guarantee no interaction between functional dependencies and NNINDs.
论文关键词：Axiomatization,Chase,Complexity,Functional dependency,Inclusion dependency,Null,Partial semantics,Simple semantics,Undecidability,SQL
论文评审过程：Received 17 December 2015, Revised 19 August 2016, Accepted 14 November 2016, Available online 22 November 2016, Version of Record 19 December 2016.
论文官网地址：https://doi.org/10.1016/j.jcss.2016.11.004
