You are previewing Foundations of Data Exchange.
O'Reilly logo
Foundations of Data Exchange

Book Description

The problem of exchanging data between different databases with different schemas is an area of immense importance. Consequently data exchange has been one of the most active research topics in databases over the past decade. Foundational questions related to data exchange largely revolve around three key problems: how to build target solutions; how to answer queries over target solutions; and how to manipulate schema mappings themselves? The last question is also known under the name 'metadata management', since mappings represent metadata, rather than data in the database. In this book the authors summarize the key developments of a decade of research. Part I introduces the problem of data exchange via examples, both relational and XML; Part II deals with exchanging relational data; Part III focuses on exchanging XML data; and Part IV covers metadata management.

Table of Contents

  1. Cover
  2. Half Title
  3. Title
  4. Copyright
  5. Dedication
  6. Contents
  7. Preface
  8. PART ONE GETTING STARTED
    1. 1 Data exchange by example
      1. 1.1 A data exchange example
      2. 1.2 Overview of the main tasks in data exchange
      3. 1.3 Data exchange vs data integration
    2. 2 Theoretical background
      1. 2.1 Relational database model
      2. 2.2 Query languages
      3. 2.3 Incomplete data
      4. 2.4 Complexity classes
      5. 2.5 Basics of automata theory
    3. 3 Data exchange: key definitions
      1. 3.1 Schema mappings
      2. 3.2 Solutions
      3. 3.3 Query answering and rewriting
      4. 3.4 Bibliographic comments
  9. PART TWO RELATIONAL DATA EXCHANGE
    1. 4 The problem of relational data exchange
      1. 4.1 Key definitions
      2. 4.2 Key problems
    2. 5 Existence of solutions
      1. 5.1 The problem and easy cases
      2. 5.2 Undecidability for st-tgds and target constraints
      3. 5.3 The chase
      4. 5.4 Weak acyclicity of target constraints
      5. 5.5 Complexity of the problem
    3. 6 Good solutions
      1. 6.1 Universal solutions
      2. 6.2 Existence of universal solutions
      3. 6.3 Canonical universal solution and chase
      4. 6.4 The core
    4. 7 Query answering and rewriting
      1. 7.1 Answering relational calculus queries
      2. 7.2 Answering conjunctive queries
      3. 7.3 Conjunctive queries with inequalities
      4. 7.4 Tractable query answering with negation
      5. 7.5 Rewritability over special solutions
      6. 7.6 Non-rewritability tool: locality
    5. 8 Alternative semantics
      1. 8.1 Universal solutions semantics
      2. 8.2 Closed-world semantics
      3. 8.3 Closed-world semantics and target constraints
      4. 8.4 Clopen-world semantics
    6. 9 Endnotes to Part Two
      1. 9.1 Summary
      2. 9.2 Bibliographic comments
      3. 9.3 Exercises
  10. PART THREE XML DATA EXCHANGE
    1. 10 The problem of XML data exchange
      1. 10.1 XML documents and schemas
      2. 10.2 Key problems of XML data exchange
    2. 11 Patterns and mappings
      1. 11.1 Tree patterns: classification and complexity
      2. 11.2 XML schema mappings and their complexity
    3. 12 Building solutions
      1. 12.1 Building solutions revisited
      2. 12.2 A simple exhaustive search algorithm
      3. 12.3 Nested-relational DTDs
      4. 12.4 The algorithm for regular schemas
      5. 12.5 The general algorithm
      6. 12.6 Combined complexity of solution building
    4. 13 Answering tuple queries
      1. 13.1 The query answering problem
      2. 13.2 An upper bound
      3. 13.3 Sources of intractability
      4. 13.4 Tractable query answering
    5. 14 XML-to-XML queries
      1. 14.1 XML-to-XML query language TQL
      2. 14.2 Notion of certain answers
      3. 14.3 Certain answers for TQL queries
      4. 14.4 XML-to-XML queries in data exchange
    6. 15 XML data exchange via relations
      1. 15.1 Translations and correctness
      2. 15.2 Translations of schemas and documents
      3. 15.3 Translations of patterns, mappings and queries
      4. 15.4 Answering XML queries using relational data exchange
    7. 16 Endnotes to Part Three
      1. 16.1 Summary
      2. 16.2 Bibliographic comments
      3. 16.3 Exercises
  11. PART FOUR METADATA MANAGEMENT
    1. 17 What is metadata management?
      1. 17.1 Reasoning about schema mappings
      2. 17.2 Manipulating schema mappings
    2. 18 Consistency of schema mappings
      1. 18.1 Problems statements
      2. 18.2 Consistency for XML
      3. 18.3 Absolute consistency for XML
    3. 19 Mapping composition
      1. 19.1 The notion of composition and key problems
      2. 19.2 Complexity of relational composition
      3. 19.3 Extending st-tgds with second-order quantification
      4. 19.4 Complexity of XML composition
      5. 19.5 Tractable XML composition
    4. 20 Inverting schema mappings
      1. 20.1 A first definition of inverse
      2. 20.2 Bringing exchanged data back: the recovery of a schema mapping
      3. 20.3 Computing the inverse operator
      4. 20.4 Inverses under extended semantics
    5. 21 Structural characterizations of schema mapping
      1. 21.1 Structural properties
      2. 21.2 Schema mapping languages characterizations
      3. 21.3 An application: simplifying schema mappings
    6. 22 Endnotes to Part Four
      1. 22.1 Summary
      2. 22.2 Bibliographic comments
      3. 22.3 Exercises
  12. References
  13. Index