The MathNet Korea
Information Center for Mathematical Science

논문검색

Information Center for Mathematical Science

논문검색

SIAM Journal on Computing
( Vol. 29 NO.5 / (2000))
Safe Constraint Queries
Michael Benedikt, Leonid Libkin,
Pages. 1652-1682
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.
Contents 1. Introduction 2. Notation 3. Safe translations 4. Range-restriction and safety 5. Deciding safety of conjunctive queries and relatives 6. Dichotomy theorem and outputs of queries 7. Preserving geometric properties of constraint databases 8. Conclusion and future work
Key words constraints, databases, first-order logic, query safety
Mathmatical Subject Classification 68P15, 03C07, 03C10, 03C13, 03