Dense-Order Constraint Databases (Extended Abstract)

Summary: Finite representations of infinite databases via dense-order constraints; study query languages (order, addition, recursion, nested sets) and give an exact PTIME characterization (data complexity) of computable dense-order queries. Show limitations—region and graph connectivity not definable with linear constraints—and extend to complex-object constraint databases under active-domain semantics, proving expressive-power and complexity profiles similar to the classical complex-object calculus. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1048
Venue: PODS
Year: 1995
Pagerank: 5.9290535e-05
Overall Rank: 4,778 | 66.77%
DOI: -

Incoming Non-self Citations Over Time

Authors

1. Stéphane Grumbach
2. Jianwen Su

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
2,357	Topological Queries in Spatial Databases	1996	PODS	8.9617862e-05
3,784	Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract)	1996	PODS	6.7697677e-05
5,709	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3602702e-05
8,323	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	4.5435639e-05

Outgoing Citations (Sorted by Pagerank)

Showing 8 of 8 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
97	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.0005080702
620	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00019005954
1,415	Towards a Theory of Spatial Database Queries (Extended Abstract)	1994	PODS	0.0001211468
1,649	Finitely Representable Databases	1994	PODS	0.00011017687
3,040	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6707607e-05
3,191	The LyriC Language: Querying Constraint Objects	1995	SIGMOD	7.4112897e-05
3,613	Completeness Results for Recursive Data Bases	1993	PODS	6.9161103e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9164359e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,835	The Expressiveness of a Family of Finite Set Languages	1991	PODS	0.00010375854
431	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023370207
5,709	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3602702e-05
3,784	Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract)	1996	PODS	6.7697677e-05
3,189	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.4116834e-05
1,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
3,040	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6707607e-05
581	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019767772
8,323	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	4.5435639e-05
12,682	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS	4.1945683e-05