Transcription
THE THEORY SCIENCEPRESS
TABLE OF CONTENTSxivxvPreface .Acknowledgements .1. .6.AND RELATIONSCHEMES.BrassTacks .Formalization of Relations .Keys .Updates to Relations .Exercises .Bibliography and Comments .OPERATORS.Boolean Operations .TheSelectOperatorThe Project Operator. .The Join Operator .Properties of Join .Exercises .Bibliography and Comments .OPERATIONSON RELATIONS.The Divide Operator .Constant Relations. .Renaming Attributes.The Equijoin Operator .Extensions for Other Comparisons on Domains .3.5.1. Extending Selection .3.5.2. The Theta-Join Operator .Relational Algebra .3.6.1. Algebraic Expressions as Mappings .3.6.2.Restricting the Set of Operators .Vii1124581011111315161822242525262729313233343536
5.8.5.9.5.10.FOR FUNCTIONAL6.3.DEPENDENCIES.Covers and Equivalence .Nonredundant Covers .Extraneous Attributes.Canonical Covers .The Structure of Nonredundant Covers .MinimumCovers.5.6.1. Direct Determination5.6.2. Computing Minimum Covers. .OptimalCovers .Annular Covers and Compound FunctionalDependencies .Exercises .Bibliography and Comments .DATABASES6.1.6.2.DEPENDENCIES.Definitions .Inference Axioms .Applying the Inference Axioms .Completeness of the Inference Axioms .Derivations and Derivation DAGs .4.5.1. RAP-DerivationSequences .4.5.2. Derivation DAGs .4.5.3. More about Derivation DAGs .Testing Membership in Ff .Exercises .Bibliography and Comments L4.1.4.2.4.3.4.4.4.5.5.TheSplitOperator.The Factor Operator .Exercises .Bibliography and Comments .AND NORMALFORMS .Databases and Database Schemes. .Normal Forms for Databases .6.2.1. First Normal Form .6.2.2. Anomalies and Data Redundancy. .6.2.3. Second Normal Form .6.2.4. Third Normal Form .Normalization through Decomposition 3949696989999101
Contents6.4.6.5.6.6.6.7.6.8.6.9.Shortcomings of Normalization through Decomposition .Normalization through Synthesis. .6.5.1. Preliminary Results for the Synthesis Algorithm .6.5.2. Developing the Synthesis Algorithm .6.5.3. Correctness and Other Properties of theSynthesisAlgorithm.Refinements of the Synthesis Algorithm. .6.5.4.Avoidable Attributes .Boyce-Codd Normal Form .6.7.1. Problems with Boyce-Codd Normal Form .Exercises .Bibliography and Comments .7. 7.7.8.7.9.7.10.7.11.DEPENDENCIES,AND 9122. . . . . 123Multivalued Dependencies. .Properties of Multivalued Dependencies .Multivalued Dependencies and FunctionalDependencies .Inference Axioms for Multivalued Dependencies .7.4.1. Multivalued Dependencies Alone .7.4.2. Functional and Multivalued Dependencies .7.4.3. Completeness of the Axioms and ComputingImplications.Fourth Normal Form .Fourth Normal Form and Enforceability ofDependencies .Join Dependencies .Project-Join Normal Form. .Embedded Join Dependencies. .Exercises .Bibliography and Comments .8. PROJECT-JOINMAPPINGS,TABLEAUX,THE CHASE 42143144ANDProject-Join Mappings. .Tableaux .8.2.1. Tableaux as Mappings .8.2.2. Representing Project-Join Mappings asTableaux .Tableaux Equivalence and Scheme Equivalence .1461461481.50151152
ment Mappings .Equivalence with Constraints. .85.1.F-rules .8.52.J-rules .TheChase .8.6.1. The Finite Church-Rosser Property .8.6.2. Equivalence of Tableaux under Constraints .8.6.3. Testing Implication of Join Dependencies .8.6.4. Testing Implication of Functional Dependencies . .8.6.5. Computing a Dependency Basis .Tableaux as Templates .Computational Properties of the Chase Computation. .Exercises .Bibliography and Comments ENTATIONTHEORY9.1.Notions of Adequate Representation. .Data-Equivalence of Database Schemes .9.2.Testing Adequate Representation and Equivalence9.3.Under Constraints .9.3.1. P Specified by Functional Dependencies Only .9.3.2.P Specified by Functional and MultivaluedDependencies .9.3.3. Testing Data-Equivalence.Exercises .9.4.9.5.Bibliography and Comments .195195208QUERY SYSTEMS .10.1. Equivalence and Completeness .10.2. Tuple Relational Calculus. .10.2.1. Tuple Calculus Formulas .10.2.2. Types, and Free and Bound Occurrences .10.2.3. Tuple Calculus Expressions .10.3. Reducing Relational Algebra with Complement to TupleRelational Calculus .10.4. Limited Interpretation of Tuple Calculus Formulas .10.4.1. Reducing Relational Algebra to Tuple Calculuswith Limited Evaluation .10.4.2 Safe Tuple Calculus Expressions .10.5. Domain Relational Calculus .10.6. Reduction of Tuple Calculus to Domain Calculus. 50255
ContentsReduction of Domain Calculus to Relational Algebra. .TableauQueries .10.8.1. Single Relation Tableau Queries .10.8.2. Tableau Queries for Restricted AlgebraicExpressions .10.8.3. Tableau Queries that Come from AlgebraicExpressions .10.8.4. Tableau Queries for Multirelation Databases .10.8.5. Tableau Set Queries .10.9. Conjunctive Queries .10.10. Exercises.10.11. Bibliography and Comments .10.7.10.8.11. MODIFICATIONLevels of Information in Query Modification .Simplifications and Common Subexpressions in AlgebraicExpressions .Optimizing Algebraic Expressions. .Query Decomposition .11.4.1. Instantiation.11.4.2. Iteration11.4.3. The Query Decomposition Algorithm. .Tableau Query Optimization .11 S. 1. Tableau Query Equivalence .11 S.2.Simple Tableau Queries .11.53.Equivalence with Constraints11.5.4. Extensions for Multiple-Relation Databases .11.5.5. Tableau Set Query Equivalence .Optimizing Conjunctive Queries . .*. .Query Modification for Distributed Databases .11.7.1. Semijoins. .11.7.2. Fragments of Relations .Exercises .Bibliography and Index. .12. NULL VALUES, PARTIALDATABASES SEMANTICS12.1.12.2.12.3.12.4.INFORMATIONAND.Nulls .Functional Dependencies and Nulls .Constraints on Nulls. .Relational Algebra and Partial Relations 2377384386
xiiContents12.4.1. Possibility Functions .12.4.2. Generalizing the Relational Operators .12.4.3. Specific Possibility Functions .Partial Information and Database Semantics. .12.5.1. Universal Relation Assumptions .12.5.2. Placeholders and Subscheme Relations .12.5.3. Database Semantics and Window Functions. .12.5.4. A Window Function Based on Joins .12.5.5. WeakInstances .12.56.Independence .12.5.7. A Further Condition on Window Functions. .Exercises .Bibliography and Comments .386389394406406408410413416422427432437ACYCYLIC DATABASE SCHEMES .13.1. Properties of Database Schemes .13.1.1. Existence of a Full Reducer .13.1.2. Equivalence of a Join Dependency toMultivalued Dependencies. .13.1.3. Unique 4NF Decomposition. .13.1.4. Pairwise Consistency Implies TotalConsistency .13.1.5. Small Intermediate Joins .13.2. Syntactic Conditions on Database Schemes .13.2.1. Acyclic Hypergraphs .13.2.2. JoinTrees. .13.2.3. The Running Intersection Property .13.3. Equivalence of Conditions .13.3.1. Graham Reduction .13.3.2. Finding Join Trees .13.3.3. The Equivalence Theorem for Acyclic DatabaseSchemes. .13.3.4. Conclusions .13.4. Exercises .13.5. Bibliography and Comments .43943943912.5.12.6.12.7.13.14.ASSORTED TOPICS .14.1. Logic and Data Dependencies .14.1.1. The World of Two-Tuple Relations .14.1.2. Equivalence of Implication for Logic andFunctional Dependencies. 548.5486488
contents xiii14.2.14.3.14.4.14.5.14.6.15.14.1.3. Adding Multivalued Dependencies. .14.1.4. Nonextendability of Results .More Data Dependencies .14.2.1. Template Dependencies .14.2.2. Examples and Counterexamples for TemplateDependencies .14.2.3. A Graphical Representation for TemplateDependencies .14.2.4. Testing Implication of TemplateDependencies .14.25. Generalized Functional Dependencies .14.2.6. Closure of Satisfaction Classes UnderProjection .Limitations of Relational Algebra .Computed Relations .14.4.1. An Example .14.4.2. Testing Expressions Containing ComputedRelations .Exercises .Bibliography and Comments 83591. . . . . . . . . . . . . . . . .593. . . . . . . . . . . . . . . . . . . .611BIBLIOGRAPHYINDEX.QUERYISBL .QUEL .SQL .QBE. .PIQUE .Bibliography and Comments .489492493494
ABOUT THE AUTHORDavid Maier received his BA degree in mathematics and computer sciencefrom the University of Oregon in 1974 and his PhD from Princeton University in 1978. For four years he was assistant professor of computer sciencewith the State University of New York at Stony Brook. He is currently assistant professor of computer science at the Oregon Graduate Center.Dr. Maier’s papers on database theory have appeared in JACM, ACM Transactions on Database Systems, and the SIAM Journal of Computing.ABOUT THE BOOKThis remarkably comprehensive new book assembles concepts and results inrelational databases theory previously scattered through journals, books,conference proceedings, and technical memoranda in one convenient source,and introduces pertinent new material not found elsewhere. The book is intended for a second course in databases, but is an excellent reference forresearchers in the field. The material covered includes relational algebra,functional dependencies, multivalued and join dependencies, normal forms,tableaux and the chase computation,representation theory, domain andtuple relational calculus, query modification, database semantics and nullvalues, acyclic database schemes, template dependencies, and computedrelations. The final chapter is a brief survey of query languages in existingrelational systems. Each chapter contains numerous examples and exercises,along with bibliographic remarks.ISBNO- ll'i89 42-0
Single Relation Tableau Queries . 262 10.8.2. Tableau Queries for Restricted Algebraic Expressions . 268 10.8.3. Tableau Queries that Come from Algebraic . ABOUT THE BOOK This remarkably comprehensive new book assembles concepts and results in relational databases theory previously scattered through journals, books, conference .
