Constraint Databases

by Kuper, Gabriel; Libkin, Leonid; Paredaens, Jan

• ISBN13: 9783540661511
• ISBN10: 3540661514
• Format: Hardcover
• Copyright: 1999-10-01
• Publisher: Springer-Verlag New York Inc

Summary

This book is the first comprehensive survey of the field of constraint databases, written by leading researchers. 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 relational 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.

Table of Contents

Introduction	1	(21)
Gabriel Kuper
Leonid Libkin
Jan Paredaens
Motivation and Framework	1	(1)
Relational Databases and First-Order Query Languages	2	(2)
Spatial Data	4	(3)
Constraint Databases	7	(1)
The CDB Model	8	(2)
Querying Constraint Databases	10	(3)
Applications	13	(2)
Historical Note	15	(6)
Part I. Theoretical Foundations
Constraint Databases, Queries, and Query Languages	21	(34)
Jan Van den Bussche
Introduction	21	(1)
Logic	21	(2)
Quantifier Elimination	23	(1)
The Constraint Database Model	23	(5)
Constraints	23	(2)
Constraint Databases	25	(2)
Testing Equality of Constraint Relations	27	(1)
Queries on Constraint Databases	28	(7)
Constraint Queries	28	(2)
Relational Calculus with Constraints	30	(3)
Computational Feasibility	33	(1)
Relational Algebra with Constraints	34	(1)
Computationally Complete Constraint Query Languages	35	(4)
Equivalence and Satisfiability	39	(4)
Conjunctive Queries with Constraints	43	(4)
Datalog with Constraints	47	(6)
Adding Negation	51	(2)
Bibliographic Notes	53	(2)
Expressive Power: The Finite Case	55	(34)
Michael Benedikt
Leonid Libkin
Introduction	55	(5)
Semantics of Constraint Queries	56	(1)
Collapse Results	57	(3)
Notation	60	(2)
Relational Databases over Infinite Structures	60	(1)
First-Order Logic	61	(1)
Genericity	62	(1)
Active Semantics	62	(4)
Natural Semantics	66	(8)
Natural-Active Collapse	66	(2)
O-Minimality	68	(1)
Natural-Active Collapse: Algorithm and Proof	69	(4)
When the Collapse Fails	73	(1)
Higher-Order Logics	74	(5)
Natural Semantics and Hybrid Logics	77	(2)
Other Techniques and Extensions	79	(5)
Conclusion	84	(1)
Bibliographic Notes	84	(5)
Expressive Power: The Infinite Case	89	(20)
Stephane Grumbach
Gabriel Kuper
Jianwen Su
Introduction	89	(1)
Complexity of First-Order Queries	89	(9)
FO + Poly	90	(2)
Encoding of Boolean Circuits	92	(2)
FO + Lin	94	(3)
FO + Lin over Restricted Databases	97	(1)
FO(<)	98	(1)
Expressive Power of First-Order Queries	98	(4)
Expressive Power of Recursive Languages	102	(4)
Datalog¬(<)	102	(2)
Datalog + Lin	104	(2)
Bibliographic Notes	106	(3)
Query Safety with Constraints	109	(22)
Michael Benedikt
Leonid Libkin
Introduction	109	(2)
Safe Constraint Queries: The Finite Case	111	(10)
Preliminaries	111	(1)
Safe Translations	112	(2)
Range-Restriction and Safety	114	(4)
Deciding Safety	118	(2)
Dichotomy Theorem and Outputs of Queries	120	(1)
Safe Constraint Queries: The Infinite Case	121	(6)
Preserving Geometric Properties	121	(1)
Safety via Coding	122	(1)
Examples of Coding	123	(3)
Decidability Results and Geometric Bounds	126	(1)
Bibliographic Notes	127	(4)
Aggregate Languages for Constraint Databases	131	(24)
Jan Chomicki
Leonid Libkin
Introduction	131	(1)
Relational and Spatial Aggregation	132	(4)
Approximating the Volume	136	(4)
Definability of Volume Operators	140	(4)
Restricted Aggregate Operators	144	(8)
Variable Independence and Closure	145	(3)
FO + Poly + Sum and Volumes of Semi-Linear Sets	148	(4)
Conclusion	152	(1)
Bibliographic Notes	153	(2)
Datalog and Constraints	155	(20)
Peter Z. Revesz
Introduction	155	(1)
Evaluation of Datalog with Constraints	155	(1)
Termination, Safety, and Data Complexity	156	(1)
Datalog with Dense Order Constraints	156	(2)
Datalog with Gap-Order Constraints	158	(5)
General Theory	158	(1)
Stratified Datalog with Gap-Order Constraints	159	(3)
Datalog with Unrestricted Gap-Order Constraints	162	(1)
Datalog with Linear Constraints	163	(1)
Datalog with Polynomial Constraints	163	(4)
Datalog with Boolean Equality Constraints	167	(2)
General Theory	167	(1)
Application: Adder Circuit	168	(1)
Bibliographic Notes	169	(6)
Part II. Spatial and Temporal Data
Geographic Information Systems	175	(24)
Gabriel Kuper
Michel Scholl
Introduction	175	(5)
What is Geographic Information?	175	(1)
Are GIS DBMS for Geographic Information?	176	(1)
Geographic Data Sources	176	(1)
GIS Applications	177	(1)
Which Spatial Operations are Expected From a GIS?	177	(2)
Brief History of GIS	179	(1)
GIS Data Models	180	(7)
Vector vs. Raster Data	181	(1)
Spatial Models and Representation of Topology	182	(3)
Sample Spatial Database Schema	185	(1)
Examples of Queries	186	(1)
Limitations of the Current Models	187	(1)
The Constraint Approach for GIS	187	(1)
Representing Spatial Data with Constraints	188	(4)
Conversion	188	(2)
Storage	190	(1)
The Constraint vs. the Vector Approach	191	(1)
Queries over Constraint Databases	192	(4)
Role of Constraints in a GIS	196	(1)
Bibliographic Notes	197	(2)
Linear-Constraint Databases	199	(32)
Marc Gyssens
Luc Vandeurzen
Dirk Van Gucht
Introduction	199	(1)
Properties of Semi-Linear Sets	200	(1)
Positive Expressiveness Results	201	(7)
Negative Expressiveness Results	208	(4)
Extensions of FO + Lin	212	(15)
Extensions of FO + Lin with Operators	213	(1)
Extension of FO + Lin with Product Variables	214	(3)
Finite Representations of Semi-Linear Sets	217	(9)
Complete Languages for FO + Poly-Expressible Linear Queries	226	(1)
Complete Languages for Linear Queries	227	(1)
Bibliographic Notes	227	(4)
Topological Queries	231	(44)
Bart Kuijpers
Victor Vianu
Introduction	231	(3)
Preliminaries	234	(2)
Languages for Topological Queries	236	(21)
The 4-Intersection Relations	236	(3)
Region-Based Languages	239	(10)
Topological Elementary Equivalence	249	(8)
Topological Invariants	257	(4)
Lossless Topological Invariants	257	(4)
Spatial Representations of Topological Information	261	(1)
Using Topological Invariants to Answer Topological Queries	261	(10)
Fixpoint Queries on Topological Invariants	262	(3)
Translating Spatial Queries to Queries on the Invariant	265	(6)
Bibliographic Notes	271	(4)
Euclidean Query Languages	275	(18)
Bart Kuijpers
Gabriel Kuper
Jan Paredaens
Introduction	275	(2)
Semi-Circular Relations	277	(2)
Query Language over Encodings of Semi-Circular Relations	279	(3)
Safe Restriction of the Language	282	(1)
Languages for Semi-Circular Relations	283	(7)
Definition of the Query Language	284	(2)
Comparison with FO + Lin	286	(2)
Comparison with FO + Poly	288	(2)
Conclusion	290	(1)
Bibliographic Notes	290	(3)
Genericity in Spatial Databases	293	(12)
Bart Kuijpers
Dirk Van Gucht
Introduction	293	(1)
Definitions and Examples	294	(3)
Undecidability Results	297	(1)
Sound and Complete Languages for Generic Queries	298	(4)
FO + Poly	298	(3)
Computable Queries	301	(1)
Bibliographic Notes	302	(3)
Linear Repeating Points	305	(14)
Pierre Wolper
Introduction	305	(1)
A Constraint Model of Temporal Databases	306	(2)
Expressiveness of the Model	307	(1)
Computing with Temporal Constraints	308	(5)
A First Approach	308	(1)
Finite Automata as Constraints	309	(3)
Computing with Lrps Represented by Automata	312	(1)
Bibliographic Notes	313	(6)
Part III. Algorithmic Aspects
Optimization Techniques	319	(16)
Stephane Grumbach
Zoe Lacroix
Philippe Rigaux
Luc Segoufin
Introduction	319	(1)
Spatial Query Processing and Optimization	320	(3)
Data Modeling	320	(1)
Query Languages	321	(1)
Query Processing	321	(1)
Query Optimization	322	(1)
Impact of the Data Format	323	(5)
Constraint Clustering	323	(2)
Orthographic Dimension	325	(3)
Query Processing	328	(5)
Alternation of Computation Modes	329	(1)
Query Pattern Recognition	330	(3)
Bibliographic Notes	333	(2)
Constraint Algebras	335	(8)
Dina Goldin
Introduction	335	(1)
FO(<)	335	(4)
Data Representation	335	(1)
Canonical Form	336	(3)
Monotone Two-Variable Constraints	339	(3)
Bibliographic Notes	342	(1)
I/O-Efficient Algorithms for CDBs	343	(22)
Sridhar Ramaswamy
Introduction	343	(2)
Dynamic Interval Management in Secondary Memory	345	(7)
Efficient Static Data Structure for Stabbing Queries	345	(3)
Dynamic Interval Management	348	(3)
Practical Aspects of Indexing Constraints	351	(1)
Constraint Join	352	(5)
One-Dimensional Join	352	(1)
Two-Dimensional Case: Rectangle Join	353	(3)
Practical Aspects of the Join	356	(1)
Lower Bounds	357	(2)
Conclusion	359	(1)
Bibliographic Notes	359	(6)
Part IV. Prototypes
The DEDALE Prototype	365	(18)
Stephane Grumbach
Philippe Rigaux
Michel Scholl
Luc Segoufin
Introduction	365	(1)
The Data Model	366	(2)
Constraint Representation and Storage with O2	368	(3)
Data Conversion: Loading and Displaying	369	(2)
The Query Language	371	(4)
Query Processing	375	(5)
Translation, Rewriting, and Evaluation	375	(2)
Constraint Manipulation	377	(2)
Implementation of Algebriac Operators	379	(1)
Conclusion	380	(1)
Bibliographic Notes	381	(2)
The DISCO System	383	(8)
Peter Revesz
Introduction	383	(1)
DISCO Queries	383	(1)
Implementation	384	(4)
Converting to Relational Algebra	384	(2)
Optimization of Relational Algebra	386	(2)
Extensibility of Disco	388	(1)
Bibliographic Notes	388	(3)
SQL/TP: A Temporal Extension of SQL	391	(10)
David Toman
Introduction	391	(1)
Temporal Data Model and Constraint Encoding	391	(2)
Representable Temporal Databases	392	(1)
Data Definition Language	392	(1)
Queries	393	(5)
Syntax and Semantics	394	(1)
Query Compilation	395	(3)
Bibliographic Notes	398	(3)
Bibliography	401	(22)
Index	423