NDLI: FirstOrder Languages Expressing Constructible Spatial Database Queries

Please wait, while we are loading the content...

FirstOrder Languages Expressing Constructible Spatial Database Queries

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Kuijpers, Bart Kuper, Gabriel Paredaens, Jan Vandeurzen, Luc
Copyright Year	2007
Abstract	The research presented in this paper is situated in the framework of constraint databases introduced by Kanellakis, Kuper, and Revesz in their seminal paper of 1990, specifically, the language with real polynomial constraints FOpoly. For reasons of efficiency, this model is implemented with only linear polynomial constraints, but this limitation to linear polynomial constraints has severe implications on the expressive power of the query language. In particular, when used for modeling spatial data, important queries that involve Euclidean distance are not expressible. The aim of this paper is to identify a class of twodimensional constraint databases and a query language within the constraint model that go beyond the linear model and allow the expression of queries concerning distance. We seek inspiration in the Euclidean constructions, i.e., constructions by ruler and compass. We first present a programming language that captures exactly the firstorder rulerandcompass constructions that are expressible in a firstorder language with real polynomial constraints. If this language is extended with a while operator, we obtain a language that is complete for all rulerandcompass constructions in the plane. We then transform this language in a natural way into a query language on finite point databases, but this language turns out to have the same expressive power as FOpoly and is therefore too powerful for our purposes. We then consider a safe fragment of this language and use this to construct a query language that allows the expression of Euclidean distance without having the full power of FOpoly.
Starting Page	1570
Ending Page	1599
Page Count	30
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539702407199
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	6
Volume Number	36
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2007-02-20
Access Restriction	Subscribed
Subject Keyword	Semialgebraic sets and related spaces constraint databases Triangulating Logic in computer science real algebraic geometry query languages Database theory Elementary problems in Euclidean geometries firstorder logic rulerandcompass constructions
Content Type	Text
Resource Type	Article
Subject	Mathematics Computer Science

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in