Foundations of Databases: The Logical Level

Written by three leading researchers in the field, this book provides in-depth coverage of the theory concerning the logical level of database management systems, including both classical and advanced topics. Features \*Emphasizes query languages for the relational model including coverage of different language paradigms, expressive power, and complexity. \*Presents a unified theory of dependencies, including those commonly arising in practice, and their use in optimization and schema design. \*Provides theoretical underpinnings of several emerging topics, including deductive and object-oriented databases. \*Includes detailed proofs and numerous examples and exercises. 0201537710B04062001 Preface......Page 8 PART A ANTECHAMBER......Page 20 1.1 The Main Principles......Page 22 1.2 Functionalities......Page 24 1.4 Past and Future......Page 26 1.5 Ties with This Book......Page 27 Bibliographic Notes......Page 28 2.1 Some Basics......Page 29 2.2 Languages, Computability, and Complexity......Page 32 2.3 Basics from Logic......Page 39 3 The Relational Model......Page 47 3.1 The Structure of the Relational Model......Page 48 3.2 Named versus Unnamed Perspectives......Page 50 3.3 Conventional versus Logic Programming Perspectives......Page 51 Bibliographic Notes......Page 53 PART B BASICS: RELATIONAL QUERY LANGUAGES......Page 54 4 Conjunctive Queries......Page 56 4.1 Getting Started......Page 57 4.2 Logic-Based Perspectives......Page 59 4.3 Query Composition and Views......Page 67 4.4 Algebraic Perspectives......Page 71 4.5 Adding Union......Page 80 Bibliographic Notes......Page 83 Exercises......Page 84 5 Adding Negation: Algebra and Calculus......Page 89 5.1 The Relational Algebras......Page 90 5.2 Nonrecursive Datalog with Negation......Page 91 5.3 The Relational Calculus......Page 92 5.4 Syntactic Restrictions for Domain Independence......Page 100 5.5 Aggregate Functions......Page 110 5.6 Digression: Finite Representations of Infinite Databases......Page 112 Bibliographic Notes......Page 115 Exercises......Page 117 6 Static Analysis and Optimization......Page 124 6.1 Issues in Practical Query Optimization......Page 125 6.2 Global Optimization......Page 134 6.3 Static Analysis of the Relational Calculus......Page 141 6.4 Computing with Acyclic Joins......Page 145 Bibliographic Notes......Page 153 Exercises......Page 155 7.1 SQL: The Structured Query Language......Page 161 7.2 Query-by-Example and Microsoft Access......Page 168 7.3 Confronting the Real World......Page 171 Exercises......Page 173 PART C CONSTRAINTS......Page 176 8.1 Motivation......Page 178 8.2 Functional and Key Dependencies......Page 182 8.3 Join and Multivalued Dependencies......Page 188 8.4 The Chase......Page 192 Bibliographic Notes......Page 204 Exercises......Page 205 9.1 Inclusion Dependency in Isolation......Page 211 9.2 Finite versus Infinite Implication......Page 216 9.3 Nonaxiomatizability of fd’s + ind’s......Page 221 9.4 Restricted Kinds of Inclusion Dependency......Page 226 Exercises......Page 230 10 A Larger Perspective......Page 235 10.1 A Unifying Framework......Page 236 10.2 The Chase Revisited......Page 239 10.3 Axiomatization......Page 245 10.4 An Algebraic Perspective......Page 247 Bibliographic Notes......Page 252 Exercises......Page 254 11 Design and Dependencies......Page 259 11.1 Semantic Data Models......Page 261 11.2 Normal Forms......Page 270 11.3 Universal Relation Assumption......Page 279 Bibliographic Notes......Page 283 Exercises......Page 285 PART D DATALOG AND RECURSION......Page 290 12 Datalog......Page 292 12.1 Syntax of Datalog......Page 295 12.2 Model-Theoretic Semantics......Page 297 12.3 Fixpoint Semantics......Page 301 12.4 Proof-Theoretic Approach......Page 305 12.5 Static Program Analysis......Page 319 Bibliographic Notes......Page 323 Exercises......Page 325 13 Evaluation of Datalog......Page 330 13.1 Seminaive Evaluation......Page 331 13.2 Top-Down Techniques......Page 335 13.3 Magic......Page 343 13.4 Two Improvements......Page 346 Bibliographic Notes......Page 354 Exercises......Page 356 14 Recursion and Negation......Page 361 14.1 Algebra + While......Page 363 14.2 Calculus + Fixpoint......Page 366 14.3 Datalog with Negation......Page 374 14.4 Equivalence......Page 379 14.5 Recursion in Practical Languages......Page 387 Bibliographic Notes......Page 388 Exercises......Page 389 15.1 The Basic Problem......Page 393 15.2 Stratified Semantics......Page 396 15.3 Well-Founded Semantics......Page 404 15.4 Expressive Power......Page 416 15.5 Negation as Failure in Brief......Page 425 Bibliographic Notes......Page 427 Exercises......Page 429 PART E EXPRESSIVENESS AND COMPLEXITY......Page 434 16.1 Queries......Page 436 16.2 Complexity of Queries......Page 441 16.3 Languages and Complexity......Page 442 Bibliographic Notes......Page 444 Exercises......Page 445 17 First Order, Fixpoint, and While......Page 448 17.1 Complexity of First-Order Queries......Page 449 17.2 Expressiveness of First-Order Queries......Page 452 17.3 Fixpoint and While Queries......Page 456 17.4 The Impact of Order......Page 465 Bibliographic Notes......Page 476 Exercises......Page 478 18 Highly Expressive Languages......Page 485 18.1 WhileN—while with Arithmetic......Page 486 18.2 Whilenew—while with New Values......Page 488 18.3 Whileuty—An Untyped Extension of while......Page 494 Bibliographic Notes......Page 498 Exercises......Page 500 PART F FINALE......Page 504 19 Incomplete Information......Page 506 19.1 Warm-Up......Page 507 19.2 Weak Representation Systems......Page 509 19.3 Conditional Tables......Page 512 19.4 The Complexity of Nulls......Page 518 19.5 Other Approaches......Page 520 Bibliographic Notes......Page 523 Exercises......Page 525 20 Complex Values......Page 527 20.1 Complex Value Databases......Page 530 20.2 The Algebra......Page 533 20.3 The Calculus......Page 538 20.4 Examples......Page 542 20.5 Equivalence Theorems......Page 545 20.6 Fixpoint and Deduction......Page 550 20.7 Expressive Power and Complexity......Page 553 20.8 A Practical Query Language for Complex Values......Page 555 Bibliographic Notes......Page 557 Exercises......Page 558 21 Object Databases......Page 561 21.1 Informal Presentation......Page 562 21.2 Formal Definition of an OODB Model......Page 566 21.3 Languages for OODB Queries......Page 575 21.4 Languages for Methods......Page 582 21.5 Further Issues for OODBs......Page 590 Bibliographic Notes......Page 592 Exercises......Page 594 22 Dynamic Aspects......Page 598 22.1 Update Languages......Page 599 22.2 Transactional Schemas......Page 603 22.3 Updating Views and Deductive Databases......Page 605 22.4 Updating Incomplete Information......Page 612 22.5 Active Databases......Page 619 22.6 Temporal Databases and Constraints......Page 625 Bibliographic Notes......Page 632 Exercises......Page 634 Bibliography......Page 640 Symbol Index......Page 677 Index......Page 679 Preface 8 PART A ANTECHAMBER 20 1 Database Systems 22 1.1 The Main Principles 22 1.2 Functionalities 24 1.3 Complexity and Diversity 26 1.4 Past and Future 26 1.5 Ties with This Book 27 Bibliographic Notes 28 2 Theoretical Background 29 2.1 Some Basics 29 2.2 Languages, Computability, and Complexity 32 2.3 Basics from Logic 39 3 The Relational Model 47 3.1 The Structure of the Relational Model 48 3.2 Named versus Unnamed Perspectives 50 3.3 Conventional versus Logic Programming Perspectives 51 3.4 Notation 53 Bibliographic Notes 53 PART B BASICS: RELATIONAL QUERY LANGUAGES 54 4 Conjunctive Queries 56 4.1 Getting Started 57 4.2 Logic-Based Perspectives 59 4.3 Query Composition and Views 67 4.4 Algebraic Perspectives 71 4.5 Adding Union 80 Bibliographic Notes 83 Exercises 84 5 Adding Negation: Algebra and Calculus 89 5.1 The Relational Algebras 90 5.2 Nonrecursive Datalog with Negation 91 5.3 The Relational Calculus 92 5.4 Syntactic Restrictions for Domain Independence 100 5.5 Aggregate Functions 110 5.6 Digression: Finite Representations of Infinite Databases 112 Bibliographic Notes 115 Exercises 117 6 Static Analysis and Optimization 124 6.1 Issues in Practical Query Optimization 125 6.2 Global Optimization 134 6.3 Static Analysis of the Relational Calculus 141 6.4 Computing with Acyclic Joins 145 Bibliographic Notes 153 Exercises 155 7 Notes on Practical Languages 161 7.1 SQL: The Structured Query Language 161 7.2 Query-by-Example and Microsoft Access 168 7.3 Confronting the Real World 171 Bibliographic Notes 173 Exercises 173 PART C CONSTRAINTS 176 8 Functional and Join Dependency 178 8.1 Motivation 178 8.2 Functional and Key Dependencies 182 8.3 Join and Multivalued Dependencies 188 8.4 The Chase 192 Bibliographic Notes 204 Exercises 205 9 Inclusion Dependency 211 9.1 Inclusion Dependency in Isolation 211 9.2 Finite versus Infinite Implication 216 9.3 Nonaxiomatizability of fd’s + ind’s 221 9.4 Restricted Kinds of Inclusion Dependency 226 Bibliographic Notes 230 Exercises 230 10 A Larger Perspective 235 10.1 A Unifying Framework 236 10.2 The Chase Revisited 239 10.3 Axiomatization 245 10.4 An Algebraic Perspective 247 Bibliographic Notes 252 Exercises 254 11 Design and Dependencies 259 11.1 Semantic Data Models 261 11.2 Normal Forms 270 11.3 Universal Relation Assumption 279 Bibliographic Notes 283 Exercises 285 PART D DATALOG AND RECURSION 290 12 Datalog 292 12.1 Syntax of Datalog 295 12.2 Model-Theoretic Semantics 297 12.3 Fixpoint Semantics 301 12.4 Proof-Theoretic Approach 305 12.5 Static Program Analysis 319 Bibliographic Notes 323 Exercises 325 13 Evaluation of Datalog 330 13.1 Seminaive Evaluation 331 13.2 Top-Down Techniques 335 13.3 Magic 343 13.4 Two Improvements 346 Bibliographic Notes 354 Exercises 356 14 Recursion and Negation 361 14.1 Algebra + While 363 14.2 Calculus + Fixpoint 366 14.3 Datalog with Negation 374 14.4 Equivalence 379 14.5 Recursion in Practical Languages 387 Bibliographic Notes 388 Exercises 389 15 Negation in Datalog 393 15.1 The Basic Problem 393 15.2 Stratified Semantics 396 15.3 Well-Founded Semantics 404 15.4 Expressive Power 416 15.5 Negation as Failure in Brief 425 Bibliographic Notes 427 Exercises 429 PART E EXPRESSIVENESS AND COMPLEXITY 434 16 Sizing Up Languages 436 16.1 Queries 436 16.2 Complexity of Queries 441 16.3 Languages and Complexity 442 Bibliographic Notes 444 Exercises 445 17 First Order, Fixpoint, and While 448 17.1 Complexity of First-Order Queries 449 17.2 Expressiveness of First-Order Queries 452 17.3 Fixpoint and While Queries 456 17.4 The Impact of Order 465 Bibliographic Notes 476 Exercises 478 18 Highly Expressive Languages 485 18.1 WhileN—while with Arithmetic 486 18.2 Whilenew—while with New Values 488 18.3 Whileuty—An Untyped Extension of while 494 Bibliographic Notes 498 Exercises 500 PART F FINALE 504 19 Incomplete Information 506 19.1 Warm-Up 507 19.2 Weak Representation Systems 509 19.3 Conditional Tables 512 19.4 The Complexity of Nulls 518 19.5 Other Approaches 520 Bibliographic Notes 523 Exercises 525 20 Complex Values 527 20.1 Complex Value Databases 530 20.2 The Algebra 533 20.3 The Calculus 538 20.4 Examples 542 20.5 Equivalence Theorems 545 20.6 Fixpoint and Deduction 550 20.7 Expressive Power and Complexity 553 20.8 A Practical Query Language for Complex Values 555 Bibliographic Notes 557 Exercises 558 21 Object Databases 561 21.1 Informal Presentation 562 21.2 Formal Definition of an OODB Model 566 21.3 Languages for OODB Queries 575 21.4 Languages for Methods 582 21.5 Further Issues for OODBs 590 Bibliographic Notes 592 Exercises 594 22 Dynamic Aspects 598 22.1 Update Languages 599 22.2 Transactional Schemas 603 22.3 Updating Views and Deductive Databases 605 22.4 Updating Incomplete Information 612 22.5 Active Databases 619 22.6 Temporal Databases and Constraints 625 Bibliographic Notes 632 Exercises 634 Bibliography 640 Symbol Index 677 Index 679

written By Three Leading Researchers In The Field, This Book Provides In-depth Coverage Of The Theory Concerning The Logical Level Of Database Management Systems, Including Both Classical And Advanced Topics.

features

1. emphasizes Query Languages For The Relational Model Including Coverage Of Different Language Paradigms, Expressive Power, And Complexity.
2. presents A Unified Theory Of Dependencies, Including Those Commonly Arising In Practice, And Their Use In Optimization And Schema Design.
3. provides Theoretical Underpinnings Of Several Emerging Topics, Including Deductive And Object-oriented Databases.
4. includes Detailed Proofs And Numerous Examples And Exercises.

booknews

an Advanced Reference-text That Deals With The Theory Which Has Developed Around The Logical Level Of Database Management Systems. It Provides A Focused Presentation Of The Core Material And Presents The Essence Of The Advanced Material In A Unified Framework. Some Of The Advanced Material Has Never Before Been Presented In Book Form. Note: Cip Shows A Subtitle, I.e., ...: The Logical Level. Annotation C. Book News, Inc., Portland, Or (booknews.com)

Over the past two decades, the theory concerning the logical level of database management systems has matured and become an elegant and robust piece of science. Foundations of Databases presents indepth coverage of this theory and surveys several emerging topics. Written by three leading researchers, this advanced text presents a unifying and contemporary perspective on the field. A major effort in writing the book has been to highlight the intuitions behind the theoretical development. This is the most comprehensive book available on database theory. It is a complete reference to both classical material and advanced topics that are otherwise scattered in sometimes hard-to-find papers. A major effort in writing the book was made to highlight the intuitions behind the theoretical development. The definitive book on the foundations and theory of database systems, including advanced topics not presented in any other survey book. Includes a comprehensive resource useful for any database researcher or practitioner that covers both fundamental and advanced topics.