Data Integration Complexity

Complexity of Various Problems in Data Integration, Sharing, and Exchange

This page is under construction.
your comments and suggestions
are welcome by
yuana AT cs DOT toronto DOT edu

Query Containment
Setting	Complexity	References
Data: Relational databases. Query: Conjunctive queries. Problem: is q contained in q'?	NP-complete.	[CM77]
Data: Relational databases. Query: Conjunctive queries with inequalities. Problem: is q contained in q'?	∏₂^p-complete.	[Klu88]
Data: Relational databases. Query: relational expressions with union and difference operators. Problem: is q contained in q'?	♠	[SY80]
Data: Relational databases. Query: Recursive and nonrecursive Datalog programs. Problem: is q contained in q'?	♠	[CV92]
Data: DLR (with regular expressions) Description Logics. Query: nonrecursive Datalog programs over arbitrary DLR concept and role expressions. Problem: is q contained in q'?	EXPTIME-complete. (logical implication in DLR with r.e. is EXPTIME-hard.) Undecidable if queries contain inequalities.	[CGL98]

Answering Queries Using Views
Setting	Complexity	References
Data: DLR description logic. Query: nonrecursive datalog program. View: defined as queries. Problem: decide whether d=(d₁,...,d_n) is in the answers of a query if only view extensions are available.	coNP-complete under closed domain assumption. EXPTIME-hard and can be done in 2EXPTIME under the open domain assumption. EXPTIME-complete for sound views and simple queries.	[CGL99]

Rewriting Queries Using Views
Setting	Complexity	References
Data: ALCNR description logic. Query: concept queries. View: concept queries or conjunctive queries over core-CLASSIC terminoloiges. Problem: maximally contained query rewriting.	PTIME for concept queries and views over core-CLASSIC terminologies.	[BLR97]
Data: Description logic TBox. Problem: Rewrite a concept description into an equivalent concept description with minimal length.	NP-complete for FL₀, ALN, and ALE. PSPACE-complete for ALC.	[BKM00]

Data Exchange
Setting	Complexity	References
Source: relational. Target: relational. Mapping: source-to-target dependencies (TGDs). Constraits: target constraints (TGDs and EGDs). Problem: universal solution and certain answers.	polynomial time for computing the universal solution and answering conjunctive queries. coNP-complete for computing certain answers of conjunctive queries with at least two inequalities.	[FKML03]
Source: XML (DTD). Target: XML (DTD). Mapping: source-to-target dependencies (between tree formulas). Constraints: DTD specifications. Query:conjunctive tree queries with descendant and union. Problem: consistency and certain answers.	EXPTIME-complete for consistency. PTIME for consistency of nested-relational. PTIME or coNP-complete for computing certain answers depending on regular expressions used in target DTDs.	[AL05]

Notes:

[AL05] M. Arenas and L. Libkin. XML data exchage: consistency and query answering. in PODS'05
[BKM00] F. Baader, R. Kusters, and R. Molitor. Rewriting concepts using terminologies. in KR'00
[BLR97] C. Beeri, A. Levy, and M. Rousset. Rewriting Queries Using Views in Description Logics. in PODS'97
[CGL98] D. Calvanese, G. De Giacomo, and M. Lenzerini. On the Decidability of Query Containment under Constraints. PODS'98
[CGL99] D. Calvanese, G. Giacomo, and M. Lenzerini. Answering queries using views in description logics. in DL'99
[CM77] A. Chandra and P. Merlin. Optimal Implementation of Conjunctive Queries in Relational Databases. ACM STOC'77
[CV92] S. Chaudhuri and M. Y. Vardi. On the equivalence of recursive and nonrecursive Datalog programs. in PODS'92
[FKML03] R. Fagin, P. Kolaitis, R. Miller, and L. Popa. Data Exchange: Semantics and Query Answering. ICDT'03
[Klu88] A. C. Klug. On Conjunctive Queries Containing Inequalities. J. of the ACM 35(1):146-160,1988
[SY80] Y. Sagiv and M. Yannakakis. Equivalences among relational expressions with the union and difference operators. J. of the ACM 27(4):633-655,1980