Constraint Databases

By: Gabriel Kuper (Editor), Leonid Libkin (Editor), Jan Paredaens (Editor)

Write A Review

Hardcover | 12 April 2000

At a Glance

Hardcover
452 Pages

Dimensions(cm)
23.5 x 15.24 x 2.54

Hardcover

$249.00

or 4 interest-free payments of $62.25 with

Ships in 5 to 7 business days

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.

Shipping

	Standard Shipping	Express Shipping
Metro postcodes:	$9.99	$14.95
Regional postcodes:	$9.99	$14.95
Rural postcodes:	$9.99	$14.95

Orders over $79.00 qualify for free shipping.

How to return your order

At Booktopia, we offer hassle-free returns in accordance with our returns policy. If you wish to return an item, please get in touch with Booktopia Customer Care.

Additional postage charges may be applicable.

Defective items

If there is a problem with any of the items received for your order then the Booktopia Customer Care team is ready to assist you.

For more info please visit our Help Centre.

You Can Find This Book In

Non-Fiction Computing & I.T.Databases Database Software Computer Programming & Software Development Programming & Scripting Languages Compilers & Interpreters Mathematics Mathematical Foundation Mathematical Logic

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

Constraint Databases

At a Glance

Hardcover

Shipping

How to return your order

Defective items

You Can Find This Book In

More in Databases

Python All-in-One For Dummies

3rd Edition

SPSS Survival Manual

7th Edition - A step by step guide to data analysis using IBM SPSS

Artificial Intelligence for Cyber Defense and Smart Policing

Artificial Intelligence of Things (AIoT)

New Standards, Technologies and Communication Systems

Blockchain and Digital Twin Enabled IoT Networks

Privacy and Security Perspectives

Computational Intelligence and Blockchain in Biomedical and Health Informatics

Deep Learning for Multimedia Processing Applications

Volume Two: Signal Processing and Pattern Recognition

Deep Learning for Multimedia Processing Applications

Volume One: Image Security and Intelligent Systems for Multimedia Processing

Deep Learning for Smart Healthcare

Trends, Challenges and Applications

Emerging Technologies and the Application of WSN and IoT

Smart Surveillance, Public Security, and Safety Challenges

Handbook of Artificial Intelligence and Wearables

Applications and Case Studies

Handbook of Intelligent and Sustainable Manufacturing

Tools, Principles, and Strategies

Industry 4.0 Key Technological Advances and Design Principles in Engineering, Education, Business, and Social Applications

Innovation in the University 4.0 System based on Smart Technologies

Intelligent Computing on IoT 2.0, Big Data Analytics, and Block Chain Technology

Intelligent Security Solutions for Cyber-Physical Systems

Machine Learning and Deep Learning in Neuroimaging Data Analysis

WSN and IoT

An Integrated Approach for Smart Applications

Engineering Lakehouses with Open Table Formats

Build scalable and efficient lakehouses with Apache Iceberg, Apache Hudi, and Delta Lake

Storytelling with Data

A Data Visualization Guide for Business Professionals, 10th Anniversary Edition

Database Systems

A Practical Approach

Tools and Applications of Data Mining

Big Data Analytics

A Practical Guide

The Data Science and Psychology

This product is categorised by