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

    Computing Queries on Linear Constraint Databases

    Database Programming Languages

    Italy. 6th - 8th September 1995


    Z. Lacroix & S. Grumbach


    We consider rational linear constraint databases, and study the problem of evaluating efficiently first-order queries with linear constraints.

    We show that although queries admit low data complexity (NC), their naive evaluation is rather inefficient.

    The computation paradigm is based on relational algebra and constraint solving.

    We focus on the former, and show that the query processing should differ drastically from classical relational databases.

    In particular, optimization strategies used for relational queries may be inadequate. We describe the problem and propose some preliminary optimization principles.


    PDF filePDF Version of this Paper (395kb)