Answering Queries Using Views, 2nd Edition

Table of contents

1. Preface to the First Edition
2. Preface to the Second Edition
3. Acknowledgments
4. Queries and Views
   1. Views
   2. Using Views in Database Systems
      1. Views and Use Cases
      2. Views and Technical Issues
   3. Answering Queries Using Views
      1. Producing All the Answers—Equivalent Rewritings
      2. Producing a Subset of the Answers—Contained Rewritings
      3. Data Exchange
   4. Relational Databases and Queries
      1. Conjunctive Queries
      2. Conjunctive Queries with Arithmetic Comparisons (CQAC)
      3. Conjunctive Queries with Negation (CQN)
      4. Unions of Conjunctive Queries
      5. Conjunctive Queries with Aggregation (CQA)
   5. The Structure of the Book
   6. Exercises
5. Query Containment and Equivalence
   1. CQ Query Containment
      1. Containment Mapping and Homomorphisms: Canonical Database
      2. Query Evaluation vs. Query Containment
   2. CQAC Query Containment
      1. Multiple Containment Mappings and Normalization: Set of Canonical Databases
      2. When Normalization is not Needed
      3. When Single Mapping Suffices—the Homomorphism Property: AC-canonical Databases
   3. CQN Query Containment
      1. Set of Canonical Databases
   4. CQA Query Containment and Equivalence
      1. MAX Queries
      2. SUM Queries
      3. More General Aggregate Operators
   5. Acyclic CQs
      1. Definition of Acyclic Queries and Special Cases
      2. Efficient Algorithm for Checking Query Containment
      3. Efficient Algorithm for Query Evaluation
   6. Query Equivalence
   7. Containment and Equivalence for Unions of Queries
   8. Exercises
6. Finding Equivalent Rewritings
   1. Preliminaries
      1. Expansion of a Rewriting
      2. Contained Rewritings
   2. CQ Queries and Views
      1. Canonical Rewritings and the Naive Algorithm
      2. Properties of the Expansion
      3. Algorithm CoreCover
   3. Acyclic CQ Views
   4. CQAC Queries and Views
      1. Algorithms for Finding Equivalent Rewritings for Queries and Views with ACs
      2. When the Homomorphism Property Holds
   5. Rewriting CQN Queries Using CQN Views
   6. CQA Queries
      1. Unfoldings of Rewritings
      2. Equivalence of Unfoldings and Rewritings
      3. Constructing Central Rewritings
      4. Non-central Rewritings
   7. Exercises
7. Maximally Contained Rewritings (MCRs)
   1. Preliminaries
      1. CQAC Queries and Views
   2. Finding MCRs for CQ Queries and Views: The MS Algorithm
      1. Finding MCDs
      2. Property of MCDs
      3. Combining MCDs—Most Relaxed Rewriting
   3. CQACs, the Homomorphism Property, Extending Algorithm MS
      1. Exportable and Distinguishable Variables of an Expansion
      2. AC-MCDs
      3. Combining AC-MCDs and MCDs, and Adding ACs
   4. Datalog
      1. Definition of the Datalog Language
      2. Views that are Unions of CQs
      3. Rewriting Datalog Queries—the Inverse-rule Algorithm (1/2)
      4. Rewriting Datalog Queries—the Inverse-rule Algorithm (2/2)
      5. CQAC-SI Queries and Views
   5. Exercises
8. Answering Queries in Presence of Dependencies
   1. Preliminaries
      1. The Chase
      2. Weakly Acyclic Sets of Tgds
      3. Property of the Chase
   2. Query Containment Under Dependencies
   3. Equivalent Rewritings
      1. Algorithm for CQ Queries, Views, and Rewritings
      2. Finding Equivalent Rewritings for Weakly Acyclic LAV Dependencies
   4. MCRs
      1. Functional Dependencies Need Recursion
      2. Inverse-rule Algorithm for Finding MCRs in Presence of Egds
   5. Exercises
9. Answering Queries in Data Exchange
   1. Complete Data Exchange
   2. Data Exchange with Arithmetic Comparisons
      1. Dependencies with Arithmetic Comparisons
      2. The AC-chase
      3. Solutions and Universal Solutions
      4. Solutions and Conjunctive Queries
      5. Query Answering
      6. When the Homomorphism Property Holds—Preliminaries
      7. Succinct AC-chase
      8. Computing Certain Answers Using Succinct AC-chase
   3. Incomplete Data Exchange
      1. Incomplete Instances
      2. The IDE Setting and the Corresponding CDE Settings
      3. Computing Certain Answers in IDE Settings
   4. Exercises
10. Answering Queries Using Views
    1. Certain Answers for Queries in Presence of View Instances
       1. Closed vs. Open World Assumption
       2. Certain Answers vs. MCRs
    2. Determinacy
       1. Definitions and Preliminaries
       2. Path Queries—Single View
       3. Path Queries—CQ is Almost Complete for Rewriting
       4. Chain Queries
11. XPath Queries and Views
    1. XML Databases and XPath Queries
    2. XPath Queries vs. Conjunctive Queries
    3. XPath Query Containment and Equivalence
    4. Definition of Extended Embedding between Patterns
    5. Containment Test for XP{//,[ ]} and XP{[ ],*}
    6. Extended Embedding is Not Enough to Prove Containment
    7. Canonical Models
    8. Containment for General Case
    9. Containment and Equivalence of Union of XPath Queries
       1. Containment Test for XP{//,*} for Single-Pattern Query
       2. Descendant Unrollings
       3. Containment Test for XP{//,*} for Union-of-Patterns Query
    10. Rewritings
        1. Pattern Composition
        2. Rewritings for Query and View in XP{[ ],*}
        3. Rewritings that are Unions of XPath Queries
    11. Conclusion and Bibliographical Notes
    12. Exercises
12. Tree-Structured Records Queried with SQL Dialect
    1. Trees as Data and as Data Types
       1. Representing Data Types and Schemas as Trees
       2. Instances of a Schema (Representing Data as Trees)
    2. Querying Tree-Structured Data
       1. Filter Queries
       2. Dominance Relation
       3. Tree-Pruning Algorithm for Filter Queries
    3. Flattening
       1. Using Flattened Data to Answer Filter Queries
    4. Discussion: Tree-Pruning vs. Flattening
       1. The Role of NULLs for Computing Legitimate Queries
    5. Flattening for Linear Schemas
    6. Aggregate Queries
    7. Conclusion and Bibliographical Notes
       1. Discussion on Related Work
13. Bibliographical Notes for Chapters 1–7
    1. Query Containment
       1. Query Containment—Set Semantics
       2. Query Containment—Bag Semantics, Aggregation
       3. Acyclicity
    2. Query Rewriting
       1. Binding Patterns
    3. Dependencies—The Chase
    4. Data Exchange
    5. Other Related Work
       1. Determinacy
       2. More Recent Related Work
14. Conclusion for Chapters 1–7
15. Bibliography (1/4)
16. Bibliography (2/4)
17. Bibliography (3/4)
18. Bibliography (4/4)
19. Authors' Biographies
20. Blank Page (1/4)
21. Blank Page (2/4)
22. Blank Page (3/4)
23. Blank Page (4/4)