The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)

Summary: Complexity analysis of positive-existential queries over databases with indefinite order information (partial orders interpreted via all linear extensions under open-world semantics with special nulls). Proves high hardness (Pi^p_2-complete containment; often intractable data complexity) and isolates PTIME fragments (monadic queries; some disjunctive cases via well-quasi-order arguments). (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: h691be3fec6fec0ce
Venue: PODS
Year: 1992
Pagerank: 0.00015243164
Overall Rank: 642 | 95.69%
DOI: 10.1145/137097.137902

Incoming Non-self Citations Over Time

Authors

1. R. van der Meyden (Rutgers University)

BibTeX Citation

@inproceedings{meyden_pods92,
        address = {New York, NY, USA},
        series = {{PODS} '92},
        title = {{The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)}},
        url = {https://dl.acm.org/doi/10.1145/137097.137902},
        doi = {10.1145/137097.137902},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {van der Meyden, R.},
        year = {1992}
}

Incoming Citations (Sorted by Pagerank)

Showing 19 of 19 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
72	Answering Queries Using Views (Extended Abstract)	1995	PODS	0.00037549176
699	Query Containment for Conjunctive Queries With Regular Expressions	1998	PODS	0.00014686953
875	Queries Independent of Updates	1993	VLDB	0.00013316445
880	Rewriting Aggregate Queries Using Views	1999	PODS	0.00013280642
914	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013104061
1,052	Answering Queries Using Limited External Query Processors	1996	PODS	0.00012275281
1,521	Constraint Checking with Partial Information	1994	PODS	0.00010379636
1,818	Deciding Containment for Queries with Complex Objects (Extended Abstract)	1997	PODS	9.5718481e-05
2,156	Obtaining Complete Answers from Incomplete Databases	1996	VLDB	8.9455055e-05
2,269	Deciding Equivalences among Aggregate Queries	1998	PODS	8.7196256e-05
2,923	Semantic Query Optimization in Datalog Programs (Extended Abstract)	1995	PODS	7.8518874e-05
3,095	Query Containment for Data Integration Systems	2000	PODS	7.6532922e-05
5,187	Equivalence of Queries Combining Set and Bag-Set Semantics	2006	PODS	6.2371772e-05
5,492	Answering Queries Using Views with Arithmetic Comparisons	2002	PODS	6.1086968e-05
5,841	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.9735439e-05
6,319	Containment of Nested XML Queries	2004	VLDB	5.8153622e-05
9,135	Equivalence of Nested Queries with Mixed Semantics	2009	PODS	5.2224867e-05
12,695	Completeness of Queries over Incomplete Databases	2011	VLDB	4.9793485e-05
12,916	Index-Based Multidimensional Array Queries: Safety and Equivalence	2007	PODS	4.9793485e-05

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
2,152	Querying Constraints	1990	PODS	8.951621e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	421	On the Complexity of Database Queries (Extended Abstract)	1997	PODS
2	658	The Complexity of Query Reliability	1998	PODS
3	8,053	Polynomial-time program transformations in deductive databases	1990	PODS
4	1,735	The Data Complexity of Consistent Query Answering for Self-Join-Free Conjunctive Queries Under Primary Key Constraints	2015	PODS
5	6,741	Inherent Complexity of Recursive Queries (Extended Abstract)	1999	PODS
6	970	On the Representation and Querying of Sets of Possible Worlds	1987	SIGMOD
7	4,592	Queries with Incomplete Answers over Semistructured Data	1999	PODS
8	1,503	The Complexity of Evaluating Relational Queries	1983	PODS
9	5,658	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS
10	3,870	On the Complexity of the Containment Problem for Conjunctive Queries with Built-in Predicates	1998	PODS