temporarily out of stock
Query Processing for Advanced Database Systems
Johann Freytag, David Maier, Gottfried Vossen
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 Series: The Morgan Kaufmann Series in Data Management Systems