Mode of access: World Wide Web.

System requirements: Adobe Acrobat Reader.

Part of: Synthesis digital library of engineering and computer science.

Includes bibliographical references (pages 201-213).

1. Queries and views -- 1.1 Views -- 1.2 Using views in database systems -- 1.2.1 Views and use cases -- 1.2.2 Views and technical issues -- 1.3 Answering queries using views -- 1.3.1 Producing all the answers--equivalent rewritings -- 1.3.2 Producing a subset of the answers--contained rewritings -- 1.3.3 Data exchange -- 1.4 Relational databases and queries -- 1.4.1 Conjunctive queries -- 1.4.2 Conjunctive queries with arithmetic comparisons (CQAC) -- 1.4.3 Conjunctive queries with negation (CQN) -- 1.4.4 Unions of conjunctive queries -- 1.4.5 Conjunctive queries with aggregation (CQA) -- 1.5 The structure of the book -- 1.6 Exercises --

2. Query containment and equivalence -- 2.1 CQ query containment -- 2.1.1 Containment mapping and homomorphisms: canonical database -- 2.1.2 Query evaluation vs. query containment -- 2.2 CQAC query containment -- 2.2.1 Multiple containment mappings and normalization: set of canonical databases -- 2.2.2 When normalization is not needed -- 2.2.3 When single mapping suffices - the homomorphism property: AC-canonical databases -- 2.3 CQN query containment -- 2.3.1 Set of canonical databases -- 2.4 CQA query containment and equivalence -- 2.4.1 MAX queries -- 2.4.2 SUM queries -- 2.4.3 More general aggregate operators -- 2.5 Acyclic CQs -- 2.5.1 Definition of acyclic queries and special cases -- 2.5.2 Efficient algorithm for checking query containment -- 2.5.3 Efficient algorithm for query evaluation -- 2.6 Query equivalence -- 2.7 Containment and equivalence for unions of queries -- 2.8 Exercises --

3. Finding equivalent rewritings -- 3.1 Preliminaries -- 3.1.1 Expansion of a rewriting -- 3.1.2 Contained rewritings -- 3.2 CQ queries and views -- 3.2.1 Canonical rewritings and the naive algorithm -- 3.2.2 Properties of the expansion -- 3.2.3 Algorithm corecover -- 3.3 Acyclic CQ views -- 3.4 CQAC queries and views -- 3.4.1 Algorithms for finding equivalent rewritings for queries and views with ACs -- 3.4.2 When the homomorphism property holds -- 3.5 Rewriting CQN queries using CQN views -- 3.6 CQA queries -- 3.6.1 Unfoldings of rewritings -- 3.6.2 Equivalence of unfoldings and rewritings -- 3.6.3 Constructing central rewritings -- 3.6.4 Non-central rewritings -- 3.7 Exercises --

4. Maximally contained rewritings (MCRs) -- 4.1 Preliminaries -- 4.1.1 CQAC queries and views -- 4.2 Finding MCRs for CQ queries and views: the MS algorithm -- 4.2.1 Finding MCDs -- 4.2.2 Property of MCDs -- 4.2.3 Combining MCDs--most relaxed rewriting -- 4.3 CQACs, the homomorphism property, extending algorithm MS -- 4.3.1 Exportable and distinguishable variables of an expansion -- 4.3.2 AC-MCDs -- 4.3.3 Combining AC-MCDs and MCDs, and adding ACs -- 4.4 Datalog -- 4.4.1 Definition of the datalog language -- 4.4.2 Views that are unions of CQs -- 4.4.3 Rewriting datalog queries-the inverse-rule algorithm -- 4.4.4 CQAC-SI queries and views -- 4.5 Exercises --

5. Answering queries in presence of dependencies -- 5.1 Preliminaries -- 5.1.1 The chase -- 5.1.2 Weakly acyclic sets of Tgds -- 5.1.3 Property of the chase -- 5.2 Query containment under dependencies -- 5.3 Equivalent rewritings -- 5.3.1 Algorithm for CQ queries, views, and rewritings -- 5.3.2 Finding equivalent rewritings for weakly acyclic LAV dependencies -- 5.4 MCRs -- 5.4.1 Functional dependencies need recursion -- 5.4.2 Inverse-rule algorithm for finding MCRs in presence of Egds -- 5.5 Exercises --

6. Answering queries in data exchange -- 6.1 Complete data exchange -- 6.2 Data exchange with arithmetic comparisons -- 6.2.1 Dependencies with arithmetic comparisons -- 6.2.2 The AC-chase -- 6.2.3 Solutions and universal solutions -- 6.2.4 Solutions and conjunctive queries -- 6.2.5 Query answering -- 6.2.6 When the homomorphism property holds--preliminaries -- 6.2.7 Succinct AC-chase -- 6.2.8 Computing certain answers using succinct AC-chase -- 6.3 Incomplete data exchange -- 6.3.1 Incomplete instances -- 6.3.2 The IDE setting and the corresponding CDE settings -- 6.3.3 Computing certain answers in IDE settings -- 6.4 Exercises --

7. Answering queries using views -- 7.1 Certain answers for queries in presence of view instances -- 7.1.1 Closed vs. open world assumption -- 7.1.2 Certain answers vs. MCRs -- 7.2 Determinacy -- 7.2.1 Definitions and preliminaries -- 7.2.2 Path queries--single view -- 7.2.3 Path queries--CQ is almost complete for rewriting -- 7.2.4 Chain queries --

8. Bibliographical notes -- 8.1 Query containment -- 8.1.1 Query containment--set semantics -- 8.1.2 Query containment--bag semantics, aggregation -- 8.1.3 Acyclicity -- 8.2 Query rewriting -- 8.2.1 Binding patterns -- 8.3 Dependencies--the chase -- 8.4 Data exchange -- 8.5 Other related work -- 8.5.1 Determinacy -- 8.5.2 More recent related work --

9. Conclusion -- Bibliography -- Authors' biographies.

Abstract freely available; full-text restricted to subscribers or individual document purchasers.

Compendex

INSPEC

Google scholar

Google book search

The topic of using views to answer queries has been popular for a few decades now, as it cuts across domains such as query optimization, information integration, data warehousing, website design, and, recently, database-as-a-service and data placement in cloud systems. This book assembles foundational work on answering queries using views in a self-contained manner, with an effort to choose material that constitutes the backbone of the research. It presents efficient algorithms and covers the following problems: query containment; rewriting queries using views in various logical languages; equivalent rewritings and maximally contained rewritings; and computing certain answers in the data-integration and data-exchange settings. Query languages that are considered are fragments of SQL, in particular, select-project-join queries, also called conjunctive queries (with or without arithmetic comparisons or negation), and aggregate SQL queries.

Also available in print.

Title from PDF title page (viewed on December 12, 2017).