Constraint Databases

1. Front Matter

   Pages I-XVII

   PDF

2. Introduction

   1. Introduction

      • Gabriel Kuper, Leonid Libkin, Jan Paredaens

      Pages 1-16

3. Theoretical Foundations

   1. Front Matter

      Pages 17-20

      PDF

   2. Constraint Databases, Queries, and Query Languages

      • Jan Van den Bussche

      Pages 21-54

   3. Expressive Power: The Finite Case

      • Michael Benedikt, Leonid Libkin

      Pages 55-87

   4. Expressive Power: The Infinite Case

      • Stéphane Grumbach, Gabriel Kuper, Jianwen Su

      Pages 89-107

   5. Query Safety with Constraints

      • Michael Benedikt, Leonid Libkin

      Pages 109-129

   6. Aggregate Languages for Constraint Databases

      • Jan Chomicki, Leonid Libkin

      Pages 131-154

   7. Datalog and Constraints

      • Peter Z. Revesz

      Pages 155-170

4. Spatial and Temporal Data

   1. Front Matter

      Pages 171-174

      PDF

   2. Geographic Information Systems

      • Gabriel Kuper, Michel Scholl

      Pages 175-198

   3. Linear-Constraint Databases

      • Marc Gyssens, Luc Vandeurzen, Dirk Van Gucht

      Pages 199-229

   4. Topological Queries

      • Bart Kuijpers, Victor Vianu

      Pages 231-273

   5. Euclidean Query Languages

      • Bart Kuijpers, Gabriel Kuper, Jan Paredaens

      Pages 275-291

   6. Genericity in Spatial Databases

      • Bart Kuijpers, Dirk Van Gucht

      Pages 293-303

   7. Linear Repeating Points

      • Pierre Wolper

      Pages 305-314

5. Algorithmic Aspects

   1. Front Matter

      Pages 315-317

      PDF

   2. Optimization Techniques

      • Stéphane Grumbach, Zoé Lacroix, Philippe Rigaux, Luc Segoufin

      Pages 319-334

   3. Constraint Algebras

      • Dina Goldin

      Pages 335-342

   4. I/O-Efficient Algorithms for CDBs

      • Sridhar Ramaswamy

      Pages 343-360

This book is the first comprehensive survey of the field of constraint databases. Constraint databases are a fairly new and active area of database research. The key idea is that constraints, such as linear or polynomial equations, are used to represent large, or even infinite, sets in a compact way. The ability to deal with infinite sets makes constraint databases particularly promising as a technology for integrating spatial and temporal data with standard re­ lational databases. Constraint databases bring techniques from a variety of fields, such as logic and model theory, algebraic and computational geometry, as well as symbolic computation, to the design and analysis of data models and query languages. The book is a collaborative effort involving many authors who have con­ tributed chapters on their fields of expertise. Despite this, the book is designed to be read as a whole, as opposed to a collection of individual surveys. In par­ ticular, the terminology and the style of presentation have been standardized, and there are multiple cross-references between the chapters. The idea of constraint databases goes back to the late Paris Kanellakis.

• Datalog
• GIS
• Logik
• SQL
• algorithms
• constraint
• constraints
• data model
• database
• databases
• logic
• optimization
• query language
• relational database
• spatial database

• Bell Labs/Lucent Technologies, Murray Hill, USA

  Gabriel Kuper, Leonid Libkin

• Department of Mathematics and Computer Science, University of Antwerp (UIA), Wilrijk-Antwerp, Belgium

  Jan Paredaens

Policies and ethics