Inclusion dependencies and their interaction with functional dependencies in SQL

详细信息    查看全文

• 作者：Henning Koehler^a ; ^{h.koehler@massey.ac.nz} ; Sebastian Link^b ; ^{s.link@auckland.ac.nz}
• 关键词：Axiomatization ; Chase ; Complexity ; Functional dependency ; Inclusion dependency ; Null ; Partial semantics ; Simple semantics ; Undecidability ; SQL
• 刊名：Journal of Computer and System Sciences
• 出版年：2017
• 出版时间：May 2017
• 年：2017
• 卷：85
• 期：Complete
• 页码：104-131
• 全文大小：677 K
• 卷排序：85

文摘

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.