Query Processing for Advanced Database Systems

1st Edition - August 1, 1993
Editors: Johann Christoph Freytag, David Maier, Gottfried Vossen
Language: English
Hardback ISBN:
9 7 8 - 1 - 5 5 8 6 0 - 2 7 1 - 7

The chapters of this book provide an excellent snapshot of current research and development activities in the area of query processing and optimization. They supply potential an… Read more

Query Processing for Advanced Database Systems

Purchase options

LIMITED OFFER

Save 50% on book bundles

Immediately download your ebook while waiting for your print delivery. No promo code is needed.

Institutional subscription on ScienceDirect

Request a sales quote

The chapters of this book provide an excellent snapshot of current research and development activities in the area of query processing and optimization. They supply potential answers to many questions that have been raised for new types of database systems and at the same time reflect the variety of the different approaches taken. The book acts both as a reference for the state of the art in query processing for the "next generation" of database systems, and as a good starting point for anybody interested in understanding the challenging questions in the area. Furthermore, the book will help the reader to gain an in-depth understanding of why efficient query processing is needed for future database systems.

Query Processing for Advanced Database Systems
Edited by Johann Christoph Freytag, David Maier, and Gottfried Vossen

PREFACE

INTRODUCTION

I EXTENDING RELATIONAL APPROACHES

1 ADT-based Type System for SQL K. Kulkarni, J. Bauer, U. Dayal, M. Kelley, J. Melton
- 1.1 Introduction
- 1.2 Type System of SQL
- 1.3 Previous Research
- 1.4 Proposed Type System for SQL
  - 1.4.1 Abstract Data Types
  - 1.4.2 Values and Objects
  - 1.4.3 Other Features
- 1.5 SQL3 Change Proposals
  - 1.5.1 Basic ADT facility
  - 1.5.2 Subtype-Supertype Hierarchies
  - 1.5.3 Polymorphism
  - 1.5.4 Parameterized Types
- 1.6 Comparison with Previous Work
- 1.7 Conclusions

2 Integration of Composite Objects into Relational Query Processing: The SQL/XNF Approach B. Mitschang and H. Pirahesh
- 2.1 Introduction
- 2.2 Motivation
- 2.3 SQL/XNF Approach to Complex Objects
  - 2.3.1 Basic Concepts, Syntax, and Semantics
  - 2.3.2 API for XNF
  - 2.3.3 Implementation Strategy and Overview
- 2.4 Relational Query Processing
  - 2.4.1 Starburst's Language Processor CORONA
  - 2.4.2 Starburst's Query Graph Model
- 2.5 Composite Object Processing
  - 2.5.1 Overview of XNF Language Processing
  - 2.5.2 Query Representation
- 2.6 Conclusion, Outlook, and Related Work

3 Query Optimization in Object Bases: Exploiting Relational Techniques A. Kemper and G. Moerkotte
- 3.1 Introduction
- 3.2 Our Object Model GOM
  - 3.2.1 Main Concepts
  - 3.2.2 The Running Example
- 3.3 Query Language
  - 3.3.1 Abstract Syntax
  - 3.3.2 The Running Example
- 3.4 Access Support Structures
  - 3.4.1 Access Support Relations
  - 3.4.2 Function Materialization
- 3.5 The (Internal) Query Representation Formats
  - 3.5.1 The Algebra
  - 3.5.2 The GOM Term Language
- 3.6 The Optimization Process
  - 3.6.1 Mimicking Term-Based Optimization Within the Algebra
  - 3.6.2 The Most Costly Normal Form
  - 3.6.3 Optimizer Strategy and Generating Alternatives
- 3.7 Conclusion

4 Optimization of Complex-Object Queries in PRIMA - Statement of Problems H. Schoning
- 4.1 Introduction
- 4.2 Basic Features of the Molecule-Atom Data Model
- 4.3 The PRIMA Architecture
- 4.4 Query Processing in the Data System
- 4.5 Evaluating CSM
- 4.6 Conclusions

5 Algebraic Query Optimization in the CoOMS Structurally Object-Oriented Database System B. Demuth, A. Geppert, T. Gorchs
- 5.1 Introduction
- 5.2 The NO^2 Data Model
  - 5.2.1 NO^2 Data Structures
  - 5.2.2 Quod, the NO^2 Query Language
  - 5.2.3 The NO^2 Algebra
- 5.3 Algebraic Optimization
- 5.4 Project Overview
- 5.5 Comparison to Related Work
- 5.6 Conclusion

II LOGIC-BASED APPROACHES

6 Query Optimization in Deductive Object Bases M. Jeusfeld and M. Staudt
- 6.1 Introduction
- 6.2 Object Bases as Deductive Databases
  - 6.2.1 The Extensional Object Base
  - 6.2.2 Deductive Object Base Theory
  - 6.2.3 Deduction and Integrity
- 6.3 Queries as Classes
- 6.4 Query Optimization Methods
  - 6.4.1 Structural Query Optimization
  - 6.4.2 Complex Object View Optimization
- 6.5 State of Implementation
- 6.6 Conclusions

7 Evaluation Aspects of an Object-oriented Deductive Database Language G. Lausen and B. Marx
- 7.1 Introduction
- 7.2 Syntax and Semantics
  - 7.2.1 Syntax
  - 7.2.2 Semantics
- 7.3 Evaluation of Programs
  - 7.3.1 Extending the T-operator
  - 7.3.2 Safety and Weak Recursive Programs
  - 7.3.3 Perfect Models of F-logic
  - 7.3.4 Reducing the Dependency Graph
- 7.4 Type Checking
- 7.5 Conclusion

8 Tagging as an Alternative to Object Creation M. Gyssens, L.V. Saxton, D. Van Gucht
- 8.1 Introduction
- 8.2 Towards a Tag-based Database Model
  - 8.2.1 The Graph-Oriented Object Database Model (GOOD)
  - 8.2.2 GOOD as Motivation for a Binary Tag-based Database Model
- 8.3 The Tarski Algebra
  - 8.3.1 Codd Relations and Mathematical Relations
  - 8.3.2 The Basic Algebra on Relations
  - 8.3.3 Tagging 8.4Simulating Other Database Models
- 8.4 Simulating Other Database Models
  - 8.4.1 Relational Model
  - 8.4.2 Nested Model
  - 8.4.3 GOOD model
- 8.5 The Extended Tarski Algebra
  - 8.5.1 While-expressions
  - 8.5.2 Generic Queries
  - 8.5.3 Computational Completeness of the Extended Tarski Algebra
- 8.6 Directions for Future Research

III OBJECT-ORIENTED AND COMPLEX OBJECT APPROACHES

9 Towards a Unification of Rewrite-based Optimization Techniques for Object-oriented Queries S. Cluet and C. Delobel
- 9.1 Introduction
- 9.2 Preliminaries
- 9.3 Motivation and Goals
- 9.4 A Simple Idea: a Typed Algebra
- 9.5 Graphical Representation of a Typed Algebra
- 9.6 A Global Representation for a Global Factorization
- 9.7 Conclusion

10 Implementation of the Object-Oriented Data Model TM H. J. Steenhagen and P. M. G. Apers
- 10.1 Introduction
- 10.2 Introduction to TM
  - 10.2.1 Example
  - 10.2.2 Conceptual Schema
  - 10.2.3 Classes
  - 10.2.4 Expressions
- 10.3 Introduction to ADL
  - 10.3.1 Data objects
  - 10.3.2 Operators
  - 10.3.3 Functionals
  - 10.3.4 Expressions
- 10.4 Translation of TM to ADL
  - 10.4.1 Translation of Classes
  - 10.4.2 Translation of TM expressions
  - 10.4.3 Example translation
- 10.5 Optimization in ADL
- 10.6 Future Work

11 Extensible Query Optimization and Parallel Execution in Volcano G. Graefe R. L. Cole, D. L. Davison, W. J. McKenna, R. H. Wolniewicz
- 11.1 Introduction
- 11.2 An Example
- 11.3 Query Optimization
- 11.4 Query Execution
- 11.5 Summary
- 11.6 Acknowledgements

12 Challenges for Query Processing in Object-Oriented Databases D. Maier, S. Daniels, T. Keller, B. Vance, G. Graefe, W. McKenna
- 12.1 Motivation
- 12.2 Utility and Drawbacks of Modeling Features
  - 12.2.1 Usefulness of New Data Model Features
  - 12.2.2 Complications Introduced by New Features
- 12.3 REVELATION Overview
- 12.4 Related Work
  - 12.4.1 Query Processing in Current Object-Oriented Database Systems
  - 12.4.2 Query Processing in Extended Relational Systems
  - 12.4.3 Object Algebras
- 12.5 The REVELATION Query Processing Architecture
  - 12.5.1 Interpreter and Schema Manager
  - 12.5.2 The Revealer
  - 12.5.3 The Optimizer
  - 12.5.4 The Query Evaluator
- 12.6 Status and Conclusion

IV ACCESS METHODS, PHYSICAL DESIGN, AND PERFORMANCE EVALUATION

13 A Survey of Indexing Techniques for Object-Oriented Databases E. Bertino
- 13.1 Introduction
- 13.2 Review of Object-Oriented Concepts
- 13.3 Index Organizations for Aggregation Graphs
- 13.4 Index Organizations for Inheritance Graphs
- 13.5 Integrated Organizations
- 13.6 Precomputation and Caching
- 13.7 Conclusions

14 Physical Database Design for an Object-Oriented Database System M. H. Scholl
- 14.1 Introduction
- 14.2 Notation and Terminology
  - 14.2.1 The COCOON Object Model
  - 14.2.2 Nested Relations as a Description of Storage Structures
- 14.3 Alternatives for Physical DB Design
  - 14.3.1 Implementing Objects
  - 14.3.2 Implementing Functions
  - 14.3.3 Implementing Types, Classes, and Inheritance
  - 14.3.4 Indexes
  - 14.3.5 The Default Physical Design
- 14.4 A Physical Design Tool
  - 14.4.1 General Approach
  - 14.4.2 Load Description
  - 14.4.3 Statistical Information
  - 14.4.4 The Optimization Process
  - 14.4.5 Experiences and Extensions
- 14.5 Query Optimization
- 14.6 Conclusion

15 An Analysis of a Dynamic Query Optimization Scheme for Different Data Distributions C. A. van den Berg and M. L. Kersten
- 15.1 Introduction
- 15.2 The Dynamic Query Processing Architecture
  - 15.2.1 The Class Manager
  - 15.2.2 The Query Processor
  - 15.2.3 The Query Scheduler
- 15.3 Dynamic Query Optimization
- 15.4 Task elimination
- 15.5 Multiple join evaluation
  - 15.5.1 Multiple join processing cost
- 15.6 Conclusions