Name
Abstract | ||
|---|---|---|
Driven by the SQL standard, we investigate simple and partial inclusion dependencies (INDs) with not null constraints. Implication of simple INDs and not null constraints is not finitely axiomatizable. We propose not null inclusion dependencies (NNINDs) that subsume simple and partial INDs, are finitely axiomatizable and PSPACE-complete to decide. NNINDs are fixed parameter-tractable in their arity, typed acyclic NNINDs are NP-hard, and tree-like NNINDs are decidable in linear time. We use a chase to decide implication for functional dependencies and acyclic NNINDs in exponential time, and identify a liberal condition that guarantees no interaction between functional dependencies and acyclic (NN)INDs. 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. |
Year | DOI | Venue |
|---|---|---|
2017 | 10.1016/j.jcss.2016.11.004 | J. Comput. Syst. Sci. |
Keywords | Field | DocType |
Axiomatization,Chase,Complexity,Functional dependency,Inclusion dependency,Null,Partial semantics,Simple semantics,Undecidability,SQL | SQL,Discrete mathematics,Acyclic dependencies principle,Combinatorics,Arity,Exponential function,Decidability,Functional dependency,Time complexity,Mathematics,Dependency theory (database theory) | Journal |
Volume | Issue | ISSN |
85 | C | 0022-0000 |
Citations | PageRank | References |
3 | 0.39 | 32 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henning Koehler | 1 | 167 | 16.06 |
| Sebastian Link | 2 | 185 | 12.50 |