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.9233349e-05
Overall Rank: 4,782 | 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,365	Topological Queries in Spatial Databases	1996	PODS	8.9531668e-05
3,787	Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract)	1996	PODS	6.7633131e-05
5,719	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3551435e-05
8,317	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	4.5392079e-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
93	Remarks on the Algebra of Non First Normal Form Relations	1982	PODS	0.00051290296
618	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00018990567
1,414	Towards a Theory of Spatial Database Queries (Extended Abstract)	1994	PODS	0.00012104556
1,648	Finitely Representable Databases	1994	PODS	0.00011007456
3,043	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6632326e-05
3,196	The LyriC Language: Querying Constraint Objects	1995	SIGMOD	7.4048386e-05
3,617	Completeness Results for Recursive Data Bases	1993	PODS	6.9095022e-05
4,793	Toward Practical Constraint Databases	1993	VLDB	5.9107617e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
1,833	The Expressiveness of a Family of Finite Set Languages	1991	PODS	0.00010365844
432	On the Complexity of Database Queries (Extended Abstract)	1997	PODS	0.00023349408
3,787	Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract)	1996	PODS	6.7633131e-05
5,719	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	5.3551435e-05
3,195	On Accessing Object-Oriented Databases: Expressive Power, Complexity, and Restrictions	1989	SIGMOD	7.4052272e-05
1,738	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010704219
3,043	Tractable Query Languages for Complex Object Databases	1991	PODS	7.6632326e-05
582	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019753367
8,317	Towards Practical Constraint Databases (Extended Abstract)	1996	PODS	4.5392079e-05
12,691	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS	4.1905499e-05