Text size
  • Small
  • Medium
  • Large
  • Standard
  • Blue text on blue
  • High contrast (Yellow text on black)
  • Blue text on beige

    Query Language Primitives for Programming with Incomplete Databases

    Database Programming Languages

    Italy. 6th - 8th September 1995


    L. Libkin


    We study the problem of choosing a suitable collection of primitives for querying databases with disjunctive information.

    Theoretical foundations for querying such databases have been developed in [11, 12].

    The main tool for querying disjunctive information has come to be known under the name of normalization.

    In this paper we show how these theoretical results can lead to practical languages for querying databases with disjunctive information.

    We discuss a collection of primitives that one may want to add to a language in order to be able to ask a variety of queries over incomplete databases (including existential and optimization queries).

    We describe a new practical and easily implementable technique for partial normalization, and show how to combine it with the known technique for space-efficient normalization.

    As the result, we demonstrate that with very little extra added to the language, one can express a variety of primitives using just one general polynomial-space iterator.

    We discuss some practical implications, including nondeterminism of the resulting language, and the implementation project.


    PDF filePDF Version of this Paper (248kb)