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: h5f045a90ea4d112b
Venue: PODS
Year: 1998
Pagerank: 6.6820595e-05
Overall Rank: 4,292 | 71.15%
DOI: 10.1145/275487.275500

Incoming Non-self Citations Over Time

Authors

1. Luc Vandeurzen (University of Limburg)
2. Marc Gyssens (University of Limburg)
3. Dirk Van Gucht (Indiana University)

BibTeX Citation

@inproceedings{vandeurzen_pods98,
        address = {New York, NY, USA},
        series = {{PODS} '98},
        title = {{An Expressive Language for Linear Spatial Database Queries (extended abstract)}},
        url = {https://dl.acm.org/doi/10.1145/275487.275500},
        doi = {10.1145/275487.275500},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Vandeurzen, Luc and Gyssens, Marc and Van Gucht, Dirk},
        year = {1998}
}

Incoming Citations (Sorted by Pagerank)

Showing 5 of 5 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
4,317	Safe Constraint Queries	1998	PODS	6.6681018e-05
4,640	Exact and Approximate Aggregation in Constraint Query Languages	1999	PODS	6.4903073e-05
6,318	Expressive power and data complexity of nonrecursive query languages for lists and trees (Extended Abstract)	2000	PODS	5.8153669e-05
13,166	Linear approximation of planar spatial databases using transitive-closure logic	2000	PODS	4.9793485e-05
13,169	Uniform Generation in Spatial Constraint Databases and Applications	2000	PODS	4.9793485e-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
914	Constraint Programming and Database Languages: A Tutorial	1995	PODS	0.00013104061
1,512	Towards a Theory of Spatial Database Queries (Extended Abstract)	1994	PODS	0.00010429539
1,950	Relational Expressive Power of Constraint Query Languages	1996	PODS	9.3195393e-05
3,612	On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)	1997	PODS	7.1626242e-05
3,667	The LyriC Language: Querying Constraint Objects	1995	SIGMOD	7.1163605e-05
4,242	Variable Independence and Aggregation Closure	1996	PODS	6.7070443e-05
4,317	Safe Constraint Queries	1998	PODS	6.6681018e-05
4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS	6.6038751e-05

Semantically Similar Papers

#	Overall Rank	Paper	Year	Venue
1	12,917	Non-Linear Prefixes in Query Languages	2007	PODS
2	3,771	Topological Queries in Spatial Databases	1996	PODS
3	6,689	Functional Database Query Languages as Typed Lambda Calculi of Fixed Order (Extended Abstract)	1994	PODS
4	4,426	Languages for Relational Databases over Interpreted Structures	1997	PODS
5	13,361	A Domain-theoretic Approach to Integrating Functional and Logic Database Languages	1993	VLDB
6	8,220	Complete geometrical query languages (extended abstract)	1997	PODS
7	13,165	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS
8	13,166	Linear approximation of planar spatial databases using transitive-closure logic	2000	PODS
9	1,919	The Expressiveness of a Family of Finite Set Languages	1991	PODS
10	3,612	On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)	1997	PODS