Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract)

Summary: Over ordered divisible Abelian groups (e.g., Q with +), every order-generic FO query collapses to a pure-order query and admits an effective rewriting eliminating +. Presents a geometric finite-representation lifting technique that uniformly translates results from finite to finitely-representable (constraint) databases via first-order reductions, showing equal expressive power. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1072
Venue: PODS
Year: 1996
Pagerank: 6.9565842e-05
Overall Rank: 4,013 | 72.47%
DOI: 10.1145/237661.237669

Incoming Non-self Citations Over Time

Authors

1. Alexei P. Stolboushkin (University of California Los Angeles)
2. Michael A. Taitslin (Tver State University)

BibTeX Citation

@inproceedings{stolboushkin_pods96,
        address = {New York, NY, USA},
        series = {{PODS} '96},
        title = {{Linear vs. Order Constraint Queries Over Rational Databases (Extended Abstract)}},
        url = {https://dl.acm.org/doi/10.1145/237661.237669},
        doi = {10.1145/237661.237669},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Stolboushkin, Alexei P. and Taitslin, Michael A.},
        year = {1996}
}

Incoming Citations (Sorted by Pagerank)

Showing 4 of 4 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,890	Relational Expressive Power of Constraint Query Languages	1996	PODS	9.5330753e-05
4,226	Safe Constraint Queries	1998	PODS	6.8211482e-05
4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.7554436e-05
5,736	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS	6.1050534e-05

Outgoing Citations (Sorted by Pagerank)

Showing 5 of 5 cited papers.

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

Rank	Cited Paper	Year	Venue	Pagerank
889	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013398105
1,890	Relational Expressive Power of Constraint Query Languages	1996	PODS	9.5330753e-05
2,241	Finitely Representable Databases	1994	PODS	8.8845324e-05
5,523	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS	6.1870017e-05
6,286	Finite Queries do not Have Effective Syntax	1995	PODS	5.9269746e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	2,110	Theory of Database Queries (Extended Abstract)	1988	PODS
2	4,226	Safe Constraint Queries	1998	PODS
3	4,336	Languages for Relational Databases over Interpreted Structures	1997	PODS
4	4,184	On Preservation under Homomorphisms and Unions of Conjunctive Queries	2004	PODS
5	12,875	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS
6	2,241	Finitely Representable Databases	1994	PODS
7	633	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS
8	5,736	On the Containment and Equivalence of Database Queries with Linear Constraints* (Extended Abstract)	1997	PODS
9	1,890	Relational Expressive Power of Constraint Query Languages	1996	PODS
10	5,523	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS