Name
Abstract | ||
|---|---|---|
Inclusion dependencies form one of the most fundamental classes of integrity constraints. Their importance in classical data management is reinforced by modern applications such as data cleaning and profiling, entity resolution and schema matching. Surprisingly, the implication problem of inclusion dependencies has not been investigated in the context of SQL, the de-facto industry standard. Codd's relational model of data represents the idealized special case of SQL in which all attributes are declared NOT NULL. Driven by the SQL standard recommendation, we investigate inclusion dependencies and NOT NULL constraints under simple and partial semantics. Partial semantics is not natively supported by any SQL implementation but we show how classical results on the implication problem carry over into this context. Interestingly, simple semantics is natively supported by every SQL implementation, but we show that the implication problem is not finitely axiomatizable in this context. Resolving this conundrum we establish an optimal solution by identifying the desirable class of not-null inclusion dependencies (NNINDs) that subsumes simple and partial semantics as special cases, and whose associated implication problem has the same computational properties as inclusion dependencies in the relational model. That is, NNIND implication is 2-ary axiomatizable and PSPACE-complete to decide. Our proof techniques bring also forward a chase procedure for deciding NNIND implication, the NP-hard subclass of typed acyclic NNINDs, and the tractable subclasses of NNINDs whose arity is bounded.
|
Year | Venue | Keywords |
|---|---|---|
2015 | CIKM | semantics,computational complexity,sql |
Field | DocType | ISBN |
SQL,Data mining,Arity,Computer science,Theoretical computer science,Data integrity,Relational model,Schema matching,Dependency theory (database theory),Null (SQL),Special case | Conference | 978-1-4503-3794-6 |
Citations | PageRank | References |
0 | 0.34 | 0 |
Authors | ||
2 | ||
Name | Order | Citations | PageRank |
|---|---|---|---|
| Henning Köhler | 1 | 13 | 1.59 |
| Sebastian Link | 2 | 185 | 12.50 |