An Expressive Language for Linear Spatial Database Queries (extended abstract)

Summary: Introduce PFOL, a coordinate-based language sound for linear FO over the reals; SPFOL (safe PFOL-fin) equals SafeEuQL and thus captures classical ruler-and-compass constructions on finite point sets. Provide finite encodings/decodings of semilinear sets and a lifting theorem that moves finite-database query languages to arbitrary linear databases, yielding a syntactic fragment of FO+poly complete for FO+poly-expressible linear queries. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1136
Venue: PODS
Year: 1998
Pagerank: 6.2427716e-05
Overall Rank: 4,366 | 69.66%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,376	Safe Constraint Queries	1998	PODS	6.233754e-05
4,719	Exact and Approximate Aggregation in Constraint Query Languages	1999	PODS	5.9659829e-05
5,516	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS	5.4685963e-05
12,692	Linear approximation of planar spatial databases using transitive-closure logic	2000	PODS	4.1905499e-05
12,695	Uniform Generation in Spatial Constraint Databases and Applications	2000	PODS	4.1905499e-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
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,738	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010704219
2,857	On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)	1997	PODS	8.009743e-05
2,973	Variable Independence and Aggregation Closure	1996	PODS	7.7895983e-05
3,196	The LyriC Language: Querying Constraint Objects	1995	SIGMOD	7.4048386e-05
4,343	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2665123e-05
4,376	Safe Constraint Queries	1998	PODS	6.233754e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,442	Non-Linear Prefixes in Query Languages	2007	PODS	4.1905499e-05
2,365	Topological Queries in Spatial Databases	1996	PODS	8.9531668e-05
6,548	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.0123519e-05
4,343	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2665123e-05
12,887	A Domain-theoretic Approach to Integrating Functional and Logic Database Languages	1993	VLDB	4.1905499e-05
7,997	Complete geometrical query languages (extended abstract)	1997	PODS	4.606843e-05
12,691	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS	4.1905499e-05
12,692	Linear approximation of planar spatial databases using transitive-closure logic	2000	PODS	4.1905499e-05
1,833	The Expressiveness of a Family of Finite Set Languages	1991	PODS	0.00010365844
2,857	On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)	1997	PODS	8.009743e-05