NDLI: Safe Constraint Queries

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

Safe Constraint Queries

Content Provider	Society for Industrial and Applied Mathematics (SIAM)
Author	Libkin, Leonid Benedikt, Michael
Copyright Year	2000
Abstract	We extend some of the classical characterization theorems of relational database theory---particularly those related to query safety---to the context where database elements come with fixed interpreted structure and where formulae over elements of that structure can be used in queries. We show that the addition of common interpreted functions, such as real addition and multiplication, to the relational calculus preserves important characterization theorems of the relational calculus and also preserves certain combinatorial properties of queries. Our main result of the first kind is that there is a syntactic characterization of the collection of safe queries over the relational calculus supplemented by a wide class of interpreted functions---a class that includes addition, multiplication, and exponentiation---and that this characterization gives us an interpreted analog of the concept of range-restricted query from the uninterpreted setting. Furthermore, our range-restricted queries are particularly intuitive for the relational calculus with real arithmetic and give a natural syntax for safe queries in the presence of polynomial functions. We use these characterizations to show that safety is decidable for Boolean combinations of conjunctive queries for a large class of interpreted structures. We show a dichotomy theorem that sets a polynomial bound on the growth of the output of a query that might refer to addition, multiplication, and exponentiation.We apply the above results for finite databases to get results on constraint databases representing potentially infinite objects. We start by getting syntactic characterizations of the queries on constraint databases that preserve geometric conditions in the constraint data model. We consider classes of convex polytopes, polyhedra, and compact semilinear sets, the latter corresponding to many spatial applications. We show how to give an effective syntax to safe queries and prove that for conjunctive queries the preservation properties are decidable.
Starting Page	1652
Ending Page	1682
Page Count	31
File Format	PDF
ISSN	00975397
DOI	10.1137/S0097539798342484
e-ISSN	10957111
Journal	SIAM Journal on Computing (SMJCAT)
Issue Number	5
Volume Number	29
Language	English
Publisher	Society for Industrial and Applied Mathematics
Publisher Date	2006-07-27
Access Restriction	Subscribed
Subject Keyword	databases Models with special properties $n$-dimensional polytopes Quantifier elimination, model completeness and related topics Basic properties of first-order languages and structures first-order logic query safety Finite structures constraints Database theory
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

First-Order Queries on Finite Structures Over the Reals

Almost $n$-ary and almost $n$-aritizable theories

Elementary equivalence in positive logic via prime products

Arities and aritizabilities of group, monoid and groupoid theories

Cell decomposition for semi-affine structures on p-adic fields

Binary simple homogeneous structures are supersimple with finite rank

Homogenizable structures and model completeness

Homogenizable structures and model completeness

Succinct Definitions in the First Order Theory of Graphs

Safe Constraint Queries

Similar Documents

First-Order Queries on Finite Structures Over the Reals

Almost $n$-ary and almost $n$-aritizable theories

Elementary equivalence in positive logic via prime products

Arities and aritizabilities of group, monoid and groupoid theories

Cell decomposition for semi-affine structures on p-adic fields

Binary simple homogeneous structures are supersimple with finite rank

Homogenizable structures and model completeness

Homogenizable structures and model completeness

Succinct Definitions in the First Order Theory of Graphs

Safe Constraint Queries