On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)

Summary: Proves decidability of whether a semi-algebraic set is semi-linear, highlights the role of coefficient types and the geometric notion of regularity, and shows regular points are computable in FO+linear. Consequence: yields a syntactic language exactly capturing the FO+poly queries that are linear, circumventing previous undecidability of testing linearity. (summarized by gpt-5-mini on Feb 09 2026)

Paper ID: 1104
Venue: PODS
Year: 1997
Pagerank: 8.009743e-05
Overall Rank: 2,857 | 80.15%
DOI: -

Incoming Non-self Citations Over Time

Authors

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Rank	Citing Paper	Year	Venue	Pagerank
1,499	Efficient Searching with Linear Constraints (Extended Abstract)	1998	PODS	0.00011643887
2,232	The DEDALE System for Complex Spatial Queries	1998	SIGMOD	9.2308835e-05
4,366	An Expressive Language for Linear Spatial Database Queries (extended abstract)	1998	PODS	6.2427716e-05
4,376	Safe Constraint Queries	1998	PODS	6.233754e-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

Outgoing Citations (Sorted by Pagerank)

Showing 4 of 4 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
3,196	The LyriC Language: Querying Constraint Objects	1995	SIGMOD	7.4048386e-05

Semantically Similar Papers

Overall Rank	Paper	Year	Venue	Pagerank
4,782	Dense-Order Constraint Databases (Extended Abstract)	1995	PODS	5.9233349e-05
582	The Complexity of Querying Indefinite Data about Linearly Ordered Domains (Preliminary Version)	1992	PODS	0.00019753367
11,561	Aggregate Queries on Sparse Databases	2020	PODS	4.1905499e-05
12,579	A characterization of first-order topological properties of planar spatial data (Extended abstract)	2004	PODS	4.1905499e-05
1,414	Towards a Theory of Spatial Database Queries (Extended Abstract)	1994	PODS	0.00012104556
12,691	Fixed-Point Query Languages for Linear Constraint Databases	2000	PODS	4.1905499e-05
2,365	Topological Queries in Spatial Databases	1996	PODS	8.9531668e-05
7,997	Complete geometrical query languages (extended abstract)	1997	PODS	4.606843e-05
4,366	An Expressive Language for Linear Spatial Database Queries (extended abstract)	1998	PODS	6.2427716e-05
12,692	Linear approximation of planar spatial databases using transitive-closure logic	2000	PODS	4.1905499e-05