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.2487721e-05
Overall Rank: 4,369 | 69.61%
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,379	Safe Constraint Queries	1998	PODS	6.2397591e-05
4,723	Exact and Approximate Aggregation in Constraint Query Languages	1999	PODS	5.9714196e-05
5,503	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS	5.4738619e-05
12,683	Linear approximation of planar spatial databases using transitive-closure logic	2000	PODS	4.1945683e-05
12,686	Uniform Generation in Spatial Constraint Databases and Applications	2000	PODS	4.1945683e-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
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,741	Relational Expressive Power of Constraint Query Languages	1996	PODS	0.00010714223
2,851	On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)	1997	PODS	8.0155027e-05
2,970	Variable Independence and Aggregation Closure	1996	PODS	7.7971058e-05
3,191	The LyriC Language: Querying Constraint Objects	1995	SIGMOD	7.4112897e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
4,379	Safe Constraint Queries	1998	PODS	6.2397591e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
12,433	Non-Linear Prefixes in Query Languages	2007	PODS	4.1945683e-05
2,357	Topological Queries in Spatial Databases	1996	PODS	8.9617862e-05
6,551	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS	5.0171671e-05
4,346	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.2725564e-05
12,877	A Domain-theoretic Approach to Integrating Functional and Logic Database Languages	1993	VLDB	4.1945683e-05
7,993	Complete geometrical query languages (extended abstract)	1997	PODS	4.6112654e-05
12,682	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS	4.1945683e-05
12,683	Linear approximation of planar spatial databases using transitive-closure logic	2000	PODS	4.1945683e-05
1,835	The Expressiveness of a Family of Finite Set Languages	1991	PODS	0.00010375854
2,851	On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)	1997	PODS	8.0155027e-05