DBScholar

Back to papers

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
1103
Venue
PODS
Year
1997
Pagerank
7.3264444e-05
Overall Rank
3,544 | 75.69%
DOI
10.1145/263661.263670

Incoming Non-self Citations Over Time

Authors

BibTeX Citation

@inproceedings{dumortier_pods97,
        address = {New York, NY, USA},
        series = {{PODS} '97},
        title = {{On the Decidability of Semi-Linearity for Semi-Algebraic Sets and its Implications for Spatial Databases (extended abstract)}},
        url = {https://dl.acm.org/doi/10.1145/263661.263670},
        doi = {10.1145/263661.263670},
        booktitle = {Proceedings of the {ACM} {SIGMOD} Symposium on {Principles} of {Database} {Systems}},
        publisher = {Association for Computing Machinery},
        author = {Dumortier, Freddy and Gyssens, Marc and Vandeurzen, Luc and Van Gucht, Dirk},
        year = {1997}
}

Incoming Citations (Sorted by Pagerank)

Showing 6 of 6 citing papers.

Previous Page 1 / 1 Next

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
889 Constraint Programming and Database Languages: A Tutorial 1995 PODS 0.00013398105
1,473 Towards a Theory of Spatial Database Queries (Extended Abstract) 1994 PODS 0.0001066845
1,890 Relational Expressive Power of Constraint Query Languages 1996 PODS 9.5330753e-05
3,591 The LyriC Language: Querying Constraint Objects 1995 SIGMOD 7.279053e-05
Previous Page 1 / 1 Next

Semantically Similar Papers