Computational Properties of Metaquerying Problems

Summary: Formalizes common metaquerying variants and maps their complexity: combined complexity is mostly intractable (unless P=NP) but identifies natural LOGCFL-complete tractable fragments. Data complexity is polynomial in general with some cases in AC^0; also analyzes metaquery equivalence for optimization. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1214
Venue: PODS
Year: 2000
Pagerank: 4.1945683e-05
Overall Rank: 12,685 | 11.76%
DOI: -

Incoming Non-self Citations Over Time

No non-self incoming citations found for this paper in this database.

Authors

Incoming Citations (Sorted by Pagerank)

Showing 0 of 0 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank

Outgoing Citations (Sorted by Pagerank)

Showing 1 of 1 cited papers.

Citations counted here include only citations to other VLDB/SIGMOD/CIDR/PODS papers in this database.

Rank	Cited Paper	Year	Venue	Pagerank
13	Mining Association Rules between Sets of Items in Large Databases	1993	SIGMOD	0.0010864752

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
2,727	Semantic Query Optimization in the Presence of Types	2010	PODS	8.2216778e-05
7,824	Optimization of Multiple-Relation Multiple-Disjunct Queries	1988	PODS	4.6418459e-05
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
10,919	Counting Answers to Unions of Conjunctive Queries: Natural Tractability Criteria and Meta-Complexity	2024	PODS	4.1945683e-05
2,243	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS	9.2166927e-05
3,462	Efficient and Provable Multi-Query Optimization	2017	PODS	7.0703696e-05
915	The Complexity of Evaluating Relational Queries	1983	PODS	0.0001538509
1,796	Summary Graphs for Relational Database Schemas	2011	VLDB	0.00010524897
571	The Complexity of Query Reliability	1998	PODS	0.00019910719
9,741	Containment of Conjunctive Object Meta-Queries	2006	VLDB	4.2936538e-05