Lecture Notes in Computer Science, 1998, Volume 1475/1998, 46-57, DOI: 10.1007/BFb0057716

Containment of conjunctive queries with built-in predicates with variables and constants over any ordered domain

Nieves R. Brisaboa, Héctor J. Hernández, José R. Paramá and Miguel R. Penabad

View Related Documents

Abstract

In this paper, we consider conjunctive queries with built-in predicates of the form X < Y, X ≤ Y, X = Y, or X ⊋ Y, where X and Y are variables or constants from a totally ordered domain. We present a sufficient and necessary condition to test containment among these kinds of queries. Klug [8] left the problem open for the case when the domain is nondense, like the integers. Ullman [11] gave only a sufficient condition for the containment of conjunctive queries with built-in predicates and integer variables. Our test is based in a method that uses a new idea: the representation of an infinite number of databases by a finite set of, what we call, canonical databases, that use variables that denote uninterpreted constants.
This work was partially supported by CICYT grant TEL96-1390-C02 and by NSF grant HRD-9628450.

Fulltext Preview

Image of the first page of the fulltext document