Eleventh Annual IEEE Symposium on

Logic in Computer Science (LICS 1996)

Paper: On the Structure of Queries in Constraint Query Languages (at LICS 1996)

Authors: Michael Benedikt Leonid Libkin


We study the structure of first-order and second-order queries over constraint databases. Constraint databases are formally modeled as finite relational structures embedded in some fixed infinite structure. We concentrate on problems of elimination of constraints, reducing quantification range to the active domain of the database and obtaining new complexity bounds. We show that for a large class of signatures, including real arithmetic constraints, unbounded quantification can be eliminated. That is, one can transform a sentence containing unrestricted quantification over the infinite universe to get an equivalent sentence in which quantifiers range over the finite relational structure. We use this result to get a new complexity upper bound on the evaluation of real arithmetic constraints. We also expand upon techniques in [21] and [4] for getting upper bounds on the expressiveness of constraint query languages, and apply it to a number of first-order and second-order query languages.


    author = 	 {Michael Benedikt and Leonid Libkin},
    title = 	 {On the Structure of Queries in Constraint Query Languages},
    booktitle =  {Proceedings of the Eleventh Annual IEEE Symp. on Logic in Computer Science, {LICS} 1996},
    year =	 1996,
    editor =	 {Edmund M. Clarke},
    month =	 {July}, 
    pages =      {25-34},
    location =   {New Brunswick, NJ, USA}, 
    publisher =	 {IEEE Computer Society Press}