Muutke küpsiste eelistusi

Constraint Databases 2000 ed. [Kõva köide]

Edited by , Edited by , Edited by
  • Formaat: Hardback, 428 pages, kõrgus x laius: 235x155 mm, kaal: 1780 g, XVII, 428 p., 1 Hardback
  • Ilmumisaeg: 12-Apr-2000
  • Kirjastus: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • ISBN-10: 3540661514
  • ISBN-13: 9783540661511
  • Kõva köide
  • Hind: 141,35 €*
  • * hind on lõplik, st. muud allahindlused enam ei rakendu
  • Tavahind: 166,29 €
  • Säästad 15%
  • Raamatu kohalejõudmiseks kirjastusest kulub orienteeruvalt 2-4 nädalat
  • Kogus:
  • Lisa ostukorvi
  • Tasuta tarne
  • Tellimisaeg 2-4 nädalat
  • Lisa soovinimekirja
  • Formaat: Hardback, 428 pages, kõrgus x laius: 235x155 mm, kaal: 1780 g, XVII, 428 p., 1 Hardback
  • Ilmumisaeg: 12-Apr-2000
  • Kirjastus: Springer-Verlag Berlin and Heidelberg GmbH & Co. K
  • ISBN-10: 3540661514
  • ISBN-13: 9783540661511
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.

This 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. Their ability to deal with infinite sets makes them 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.
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