Foundations of Databases

Preface......Page 8
Contents......Page 14
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