Advanced Database Systems
- 1st Edition - May 1, 1997
- Latest edition
- Authors: Carlo Zaniolo, Stefano Ceri, Christos Faloutsos, Richard T. Snodgrass, V.S. Subrahmanian, Roberto Zicari
- Language: English
The database field has experienced a rapid and incessant growth since the development of relational databases. The progress in database systems and applications has produced a di… Read more
Purchase options
The database field has experienced a rapid and incessant growth since the development of relational databases. The progress in database systems and applications has produced a diverse landscape of specialized technology
areas that have often become the exclusive domain of research specialists. Examples include active databases, temporal databases, object-oriented databases, deductive databases, imprecise reasoning and queries, and multimedia information systems. This book provides a systematic introduction to and an in-depth treatment of these advanced database areas. It supplies practitioners and researchers with authoritative coverage of
recent technological advances that are shaping the future of commercial database systems and intelligent information systems.
Advanced Database Systems was written by a team of six leading specialists who have made significant contributions to the development of the technology areas covered in the book. Benefiting from the authors' long experience teaching graduate and professional courses, this book is designed to provide a gradual introduction to advanced research topics and includes many examples and exercises to support its use for individual study, desk reference, and graduate classroom teaching.
Advanced Database System
by Carlo Zaniolo, Stefano Ceri, Christos Faloutsos, Richard T. Snodgrass, V.S. Subrahmanian, and Roberto Zicari
Preface
1 Introduction
Part I Active Databases
2 Syntax and Semantics of Active Databases
2.1 Starburst
2.1.1 Syntax of the Starburst CREATE RULE Statement
2.1.2 Semantics of Active Rules in Starburst
2.1.3 Other Active Rule Commands
2.1.4 Examples of Active Rule Executions
2.2 Oracle
2.2.1 Syntax of the Oracle CREATE TRIGGER Statement
2.2.2 Semantics of Oracles Triggers
2.2.3 Example of Trigger Executions
2.3 DB2
2.3.1 Syntax of the DB2 CREATE TRIGGER Statement
2.3.2 Semantics of DB2 Triggers
2.3.3. Examples of Trigger Executions
2.4 Chimera
2.4.1 Summary of Chimera
2.4.2 Syntax of the Chimera Define Trigger Statement
2.4.3 Semantics of Chimera Triggers
2.4.4 Examples of Trigger Executions
2.5 Taxonomy of Active Database Concepts
2.6 Bibliographic Notes
2.7 Exercises
3 Applications of Active Databases
3.1 Integrity Management
3.1.1 Rule Generation
3.1.2 Example
3.2 Derived Data Maintenance
3.2.1 Rule Generation
3.2.2 Example
3.3 Replication
3.4 Workflow Management
3.5 Business Rules
3.5.1 A Case Study: Energy Management System (EMS)
3.5.2 Database Schema for the EMS Case Study
3.5.3 Business Rules for the EMS Case Study
3.6 Bibliographic Notes
3.7 Exercises
4 Design Principles for Active Rules
4.1 Properties of Active Rule Execution
4.1.1 Termination
4.1.2 Confluence
4.1.3 Observable Determinism
4.2 Rule Modularization
4.2.1 Behavioral Stratification
4.2.2 Assertional Stratification
4.2.3 Event-Based Stratification
4.3 Rule Debugging and Monitoring
4.4 IDEA Methodology
4.4.1 Active Rule Design
4.4.2 Active Rule Prototyping
4.4.3 Active Rule Implementation
4.4.4 Design Tools Supporting the IDEA Methodology
4.5 Summary and Open Problems
4.6 Bibliographic Notes
4.7 Exercises
Part II Temporal Databases
5 Overview of Temporal Databases
5.1 A Case Study
5.1.1 Temporal Projection
5.1.2 Temporal Join
5.1.3 Summary
5.2 The Time Domain
5.3 Time Data Types
5.4 Associating Facts with Time
5.4.1 Dimensionality
5.4.2 Underlying Data Model
5.4.3 Representative Data Models
5.5 Temporal Query Languages
5.6 Summary
5.7 Bibliographic Notes
5.8 Exercises
6 TSQL2
6.1 Time Ontology
6.2 Data Model
6.3 Language Constructs
6.3.1 Schema Definition
6.3.2 The SELECT Statement
6.3.3 Restructuring
6.3.4 Partitioning
6.3.5 The VALID Clause
6.3.6 The Modification Statements
6.3.7 Event Relations
6.3.8 Transaction-Time Support
6.3.9 Aggregates
6.3.10 Schema Evolution and Versioning
6.4 Other Constructs
6.5 Summary
6.6 Bibliographic Notes
6.7 Exercises
7 Implementation
7.1 System Architecture
7.2 Adding Temporal Support
7.2.1 DDL Compiler
7.2.2 Query Compiler
7.2.3 Run-Time Evaluator
7.3 Minimal support Needed for TSQL2
7.3.1 Data Dictionary and Data Files
7.3.2 DDL Compiler
7.3.3 Query Compiler
7.3.4 Run-Time Evaluator
7.3.5 Transaction and Data Manager
7.4 Summary and Open Problems
7.5 Bibliographic Notes
7.6 Exercises
Part III Complex Queries and Reasoning
8 The Logic of Query Languages
8.1 Datalog
8.2 Relational Calculi
8.3 Relational Algebra
8.4 From Safe Datalog to Relational Algebra
8.4.1 Commercial Query Languages
8.5 Recursive Rules
8.6 Stratification
8.7 Expressive Power and Data Complexity
8.8 Syntax and Semantics of Datalog Languages
8.8.1 Syntax of First-Order Logic and Datalog
8.8.2 Semantics
8.8.3 Interpretations
8.9 The Models of a Program
8.10 Fixpoint-Based Semantics
8.10.1 Operational Semantics: Powers of Tp
8.11 Bibliographic Notes
8.12 Exercises
9 Implementation of Rules and Recursion
9.1 Operational Semantics: Bottom-Up Execution
9.2 Stratified Programs and Iterated Fixpoint
9.3 Differential Fixpoint Computation
9.4 Top-Down Execution
9.4.1 Unification
9.4.2 SLD-Resolution
9.5 Rule-Rewriting Methods
9.5.1 Left-Linear and Right-Linear Recursion
9.5.2 Magic Sets Method
9.5.3 The Counting Method
9.5.4 Supplementary Magic Sets
9.6 Compilation and Optimization
9.6.1 Nonrecursive Programs
9.6.2 Recursive Predicates
9.6.3 Selecting a Method for Recursion
9.6.4 Optimization Strategies and Execution Plan
9.7 Recursive Queries in SQL
9.7.1 Implementation of Recursive SQL Queries
9.8 Bibliographic Notes
9.9 Exercises
10 Database Updates and Nonmonotonic Reasoning
10.1 Nonmonotonic Reasoning
10.2 Stratification and Well-Founded Methods
10.2.1 Locally Stratified Programs
10.2.2 Well-Founded Models
10.3 Datalog (1s) and Temporal Reasoning
10.4 XY-Stratification
10.5 Updates and Active Rules
10.6 Nondeterministic Reasoning
10.7 Research Directions
10.8 Bibliographic Notes
10.9 Exercises
Part IV Spatial, Text, and Multimedia Databases
11 Traditional Indexing Methods
11.1 Secondary Keys
11.1.1 Inverted Files
11.1.2 Grid File
11.1.3 k-D Trees
11.1.4 Conclusions
11.2 Spatial Access Methods (SAMs)
11.2.1 Space-Filling Curves
11.2.2 R-Trees
11.2.3 Transforming to Higher-D Points
11.2.4 Conclusions
11.3 Text Retrieval
11.3.1 Full Text Scanning
11.3.2 Inversion
11.3.3 Signature Files
11.3.4 Vector Space Model and Clustering
11.3.5 Conclusions
11.4 Summary and Future Research
11.5 Bibliographic Notes
11.6 Exercises
12 Multimedia Indexing
12.1 Basic Idea
12.2 GEMINI for Whole Match Queries
12.3 1-D Time Series
12.3.1 Distance Function
12.3.2 Feature Extraction and Lower-Bounding
12.3.3 Introduction to DFT
12.3.4 Energy-Concentrating Properties of DFT
12.3.5 Experiments
12.4 2-D Color Images
12.4.1 Image Features and Distance Functions
12.4.2 Lower-Bounding
12.4.3 Experiments and Conclusions
12.5 Subpattern Matching
12.5.1 Sketch of the Approach—ST-Index
12.5.2 Experiments
12.6 Summary and Future Research
12.7 Bibliographic Notes
12.8 Exercises
Part V Uncertainty in Databases and Knowledge Bases
13 Models of Uncertainty
13.1 Introduction
13.1.1 Uncertainty in DBs: An Image Database Example
13.1.2 Uncertainty in DBs: A Temporal Database Example
13.1.3 Uncertainty in DBs: A Null-Value Example
13.2 Models of Uncertainty
13.2.1 Fuzzy Sets
13.2.2 Lattice-Based Approaches
13.2.3 Relationship to Fuzzy Logic
13.2.4 Probability Theory
13.3 Bibliographic Notes
13.4 Exercises
14 Uncertainty in Relational Databases
14.1 Lattice-Based Relational Databases
14.1.1 An Example
14.1.2 Querying Lattice-Based Databases
14.2 Probabilistic Relational Databases
14.2.1 Probabilistic Relations
14.2.2 Annotated Relations
14.2.3 Converting Probabilistic Tuples to Annotated Tuples
14.2.4 Manipulating Annotated Relations
14.2.5 Querying Probabilisitc Databases
14.3 Bibliographic Notes
14.4 A Final Note
14.5 Exercises
15 Including Uncertainty in Deductive Databases
15.1 Generalized Annotated Programs (GAPs)
15.1.1 Lattice-Based KBs: Model Theory
15.1.2 Lattice-Based KBs: Fixpoint Theory
15.1.3 Lattice-Based KBs: Query Processing
15.2 Probabilisic Knowledge Bases
15.2.1 Probabilistic KBs: Fixpoint Theory
15.2.2 Probabilistic KBs: Model Theory
15.2.3 Probabilistic KBs: Query Processing
15.3 Bibliographic Notes
15.4 Research Directions
15.5 Summary
15.6 Exercises
Part VI Schema and Database Evolution in Object Database Systems
16 Object Databases and Change Management
16.1 Why Changes Are Needed
16.2 The Essence of Object Databases
16.2.1 Basics of Object Databases
16.2.2 Standards
16.2.3 Change Management in Object Database Systems
16.3 Bibliographic Notes
16.4 Exercises
17 How to Change the Schema
17.1 Changing the Schema Using Primitives
17.1.1 Taxonomy of Schema Modifications
17.1.2 Schema Evolution Primitives in O2
17.2 Schema Invariants
17.3 Semantics of Schema Modifications
17.4 Bibliographic Notes
17.5 Exercises
18 How to Change the Database
18.1 Immediate vs. Deferred Transformations
18.1.1 Immediate Database Trasformation
18.1.2 Deferred Database Transformation
18.2 Preserving Structural Consistency
18.2.1 Structural Consistency Preserving Primitives
18.2.2 Structural Consistency Modifying Primitives
18.3 User-Defined and Default Transformations
18.3.1 Default Database Transformations
18.3.2 User-Defined Database Transformations
18.3.3 User-Defined Object Migration Functions
18.4 Implementing Database Updates in O2
18.4.1 Problems with Deferred Database Transformations
18.4.2 Data Structures
18.4.3 the Deferred Database Update Algorithm
18.5 Related Work
18.6 Bibliographic Notes
18.7 Exercises
19 How to Change the Database Fast
19.1 Factors Influencing the Performance of a Database Transformation
19.1.1 Immediate Database Tranformation
19.1.2 Deferred Transformation
19.1.3 Hybrid
19.2 How to Benchmark Database Updates
19.2.1 Basic Benchmark Organization
19.2.2 How to Run the Benchmark
19.3 Performance Evaluation
19.3.1 Small Databases
19.3.2 Large Databases
19.4 Open Problems
19.5 Bibliographic Notes
Bibliography
Author Index
Subject Index
by Carlo Zaniolo, Stefano Ceri, Christos Faloutsos, Richard T. Snodgrass, V.S. Subrahmanian, and Roberto Zicari
Preface
1 Introduction
Part I Active Databases
2 Syntax and Semantics of Active Databases
2.1 Starburst
2.1.1 Syntax of the Starburst CREATE RULE Statement
2.1.2 Semantics of Active Rules in Starburst
2.1.3 Other Active Rule Commands
2.1.4 Examples of Active Rule Executions
2.2 Oracle
2.2.1 Syntax of the Oracle CREATE TRIGGER Statement
2.2.2 Semantics of Oracles Triggers
2.2.3 Example of Trigger Executions
2.3 DB2
2.3.1 Syntax of the DB2 CREATE TRIGGER Statement
2.3.2 Semantics of DB2 Triggers
2.3.3. Examples of Trigger Executions
2.4 Chimera
2.4.1 Summary of Chimera
2.4.2 Syntax of the Chimera Define Trigger Statement
2.4.3 Semantics of Chimera Triggers
2.4.4 Examples of Trigger Executions
2.5 Taxonomy of Active Database Concepts
2.6 Bibliographic Notes
2.7 Exercises
3 Applications of Active Databases
3.1 Integrity Management
3.1.1 Rule Generation
3.1.2 Example
3.2 Derived Data Maintenance
3.2.1 Rule Generation
3.2.2 Example
3.3 Replication
3.4 Workflow Management
3.5 Business Rules
3.5.1 A Case Study: Energy Management System (EMS)
3.5.2 Database Schema for the EMS Case Study
3.5.3 Business Rules for the EMS Case Study
3.6 Bibliographic Notes
3.7 Exercises
4 Design Principles for Active Rules
4.1 Properties of Active Rule Execution
4.1.1 Termination
4.1.2 Confluence
4.1.3 Observable Determinism
4.2 Rule Modularization
4.2.1 Behavioral Stratification
4.2.2 Assertional Stratification
4.2.3 Event-Based Stratification
4.3 Rule Debugging and Monitoring
4.4 IDEA Methodology
4.4.1 Active Rule Design
4.4.2 Active Rule Prototyping
4.4.3 Active Rule Implementation
4.4.4 Design Tools Supporting the IDEA Methodology
4.5 Summary and Open Problems
4.6 Bibliographic Notes
4.7 Exercises
Part II Temporal Databases
5 Overview of Temporal Databases
5.1 A Case Study
5.1.1 Temporal Projection
5.1.2 Temporal Join
5.1.3 Summary
5.2 The Time Domain
5.3 Time Data Types
5.4 Associating Facts with Time
5.4.1 Dimensionality
5.4.2 Underlying Data Model
5.4.3 Representative Data Models
5.5 Temporal Query Languages
5.6 Summary
5.7 Bibliographic Notes
5.8 Exercises
6 TSQL2
6.1 Time Ontology
6.2 Data Model
6.3 Language Constructs
6.3.1 Schema Definition
6.3.2 The SELECT Statement
6.3.3 Restructuring
6.3.4 Partitioning
6.3.5 The VALID Clause
6.3.6 The Modification Statements
6.3.7 Event Relations
6.3.8 Transaction-Time Support
6.3.9 Aggregates
6.3.10 Schema Evolution and Versioning
6.4 Other Constructs
6.5 Summary
6.6 Bibliographic Notes
6.7 Exercises
7 Implementation
7.1 System Architecture
7.2 Adding Temporal Support
7.2.1 DDL Compiler
7.2.2 Query Compiler
7.2.3 Run-Time Evaluator
7.3 Minimal support Needed for TSQL2
7.3.1 Data Dictionary and Data Files
7.3.2 DDL Compiler
7.3.3 Query Compiler
7.3.4 Run-Time Evaluator
7.3.5 Transaction and Data Manager
7.4 Summary and Open Problems
7.5 Bibliographic Notes
7.6 Exercises
Part III Complex Queries and Reasoning
8 The Logic of Query Languages
8.1 Datalog
8.2 Relational Calculi
8.3 Relational Algebra
8.4 From Safe Datalog to Relational Algebra
8.4.1 Commercial Query Languages
8.5 Recursive Rules
8.6 Stratification
8.7 Expressive Power and Data Complexity
8.8 Syntax and Semantics of Datalog Languages
8.8.1 Syntax of First-Order Logic and Datalog
8.8.2 Semantics
8.8.3 Interpretations
8.9 The Models of a Program
8.10 Fixpoint-Based Semantics
8.10.1 Operational Semantics: Powers of Tp
8.11 Bibliographic Notes
8.12 Exercises
9 Implementation of Rules and Recursion
9.1 Operational Semantics: Bottom-Up Execution
9.2 Stratified Programs and Iterated Fixpoint
9.3 Differential Fixpoint Computation
9.4 Top-Down Execution
9.4.1 Unification
9.4.2 SLD-Resolution
9.5 Rule-Rewriting Methods
9.5.1 Left-Linear and Right-Linear Recursion
9.5.2 Magic Sets Method
9.5.3 The Counting Method
9.5.4 Supplementary Magic Sets
9.6 Compilation and Optimization
9.6.1 Nonrecursive Programs
9.6.2 Recursive Predicates
9.6.3 Selecting a Method for Recursion
9.6.4 Optimization Strategies and Execution Plan
9.7 Recursive Queries in SQL
9.7.1 Implementation of Recursive SQL Queries
9.8 Bibliographic Notes
9.9 Exercises
10 Database Updates and Nonmonotonic Reasoning
10.1 Nonmonotonic Reasoning
10.2 Stratification and Well-Founded Methods
10.2.1 Locally Stratified Programs
10.2.2 Well-Founded Models
10.3 Datalog (1s) and Temporal Reasoning
10.4 XY-Stratification
10.5 Updates and Active Rules
10.6 Nondeterministic Reasoning
10.7 Research Directions
10.8 Bibliographic Notes
10.9 Exercises
Part IV Spatial, Text, and Multimedia Databases
11 Traditional Indexing Methods
11.1 Secondary Keys
11.1.1 Inverted Files
11.1.2 Grid File
11.1.3 k-D Trees
11.1.4 Conclusions
11.2 Spatial Access Methods (SAMs)
11.2.1 Space-Filling Curves
11.2.2 R-Trees
11.2.3 Transforming to Higher-D Points
11.2.4 Conclusions
11.3 Text Retrieval
11.3.1 Full Text Scanning
11.3.2 Inversion
11.3.3 Signature Files
11.3.4 Vector Space Model and Clustering
11.3.5 Conclusions
11.4 Summary and Future Research
11.5 Bibliographic Notes
11.6 Exercises
12 Multimedia Indexing
12.1 Basic Idea
12.2 GEMINI for Whole Match Queries
12.3 1-D Time Series
12.3.1 Distance Function
12.3.2 Feature Extraction and Lower-Bounding
12.3.3 Introduction to DFT
12.3.4 Energy-Concentrating Properties of DFT
12.3.5 Experiments
12.4 2-D Color Images
12.4.1 Image Features and Distance Functions
12.4.2 Lower-Bounding
12.4.3 Experiments and Conclusions
12.5 Subpattern Matching
12.5.1 Sketch of the Approach—ST-Index
12.5.2 Experiments
12.6 Summary and Future Research
12.7 Bibliographic Notes
12.8 Exercises
Part V Uncertainty in Databases and Knowledge Bases
13 Models of Uncertainty
13.1 Introduction
13.1.1 Uncertainty in DBs: An Image Database Example
13.1.2 Uncertainty in DBs: A Temporal Database Example
13.1.3 Uncertainty in DBs: A Null-Value Example
13.2 Models of Uncertainty
13.2.1 Fuzzy Sets
13.2.2 Lattice-Based Approaches
13.2.3 Relationship to Fuzzy Logic
13.2.4 Probability Theory
13.3 Bibliographic Notes
13.4 Exercises
14 Uncertainty in Relational Databases
14.1 Lattice-Based Relational Databases
14.1.1 An Example
14.1.2 Querying Lattice-Based Databases
14.2 Probabilistic Relational Databases
14.2.1 Probabilistic Relations
14.2.2 Annotated Relations
14.2.3 Converting Probabilistic Tuples to Annotated Tuples
14.2.4 Manipulating Annotated Relations
14.2.5 Querying Probabilisitc Databases
14.3 Bibliographic Notes
14.4 A Final Note
14.5 Exercises
15 Including Uncertainty in Deductive Databases
15.1 Generalized Annotated Programs (GAPs)
15.1.1 Lattice-Based KBs: Model Theory
15.1.2 Lattice-Based KBs: Fixpoint Theory
15.1.3 Lattice-Based KBs: Query Processing
15.2 Probabilisic Knowledge Bases
15.2.1 Probabilistic KBs: Fixpoint Theory
15.2.2 Probabilistic KBs: Model Theory
15.2.3 Probabilistic KBs: Query Processing
15.3 Bibliographic Notes
15.4 Research Directions
15.5 Summary
15.6 Exercises
Part VI Schema and Database Evolution in Object Database Systems
16 Object Databases and Change Management
16.1 Why Changes Are Needed
16.2 The Essence of Object Databases
16.2.1 Basics of Object Databases
16.2.2 Standards
16.2.3 Change Management in Object Database Systems
16.3 Bibliographic Notes
16.4 Exercises
17 How to Change the Schema
17.1 Changing the Schema Using Primitives
17.1.1 Taxonomy of Schema Modifications
17.1.2 Schema Evolution Primitives in O2
17.2 Schema Invariants
17.3 Semantics of Schema Modifications
17.4 Bibliographic Notes
17.5 Exercises
18 How to Change the Database
18.1 Immediate vs. Deferred Transformations
18.1.1 Immediate Database Trasformation
18.1.2 Deferred Database Transformation
18.2 Preserving Structural Consistency
18.2.1 Structural Consistency Preserving Primitives
18.2.2 Structural Consistency Modifying Primitives
18.3 User-Defined and Default Transformations
18.3.1 Default Database Transformations
18.3.2 User-Defined Database Transformations
18.3.3 User-Defined Object Migration Functions
18.4 Implementing Database Updates in O2
18.4.1 Problems with Deferred Database Transformations
18.4.2 Data Structures
18.4.3 the Deferred Database Update Algorithm
18.5 Related Work
18.6 Bibliographic Notes
18.7 Exercises
19 How to Change the Database Fast
19.1 Factors Influencing the Performance of a Database Transformation
19.1.1 Immediate Database Tranformation
19.1.2 Deferred Transformation
19.1.3 Hybrid
19.2 How to Benchmark Database Updates
19.2.1 Basic Benchmark Organization
19.2.2 How to Run the Benchmark
19.3 Performance Evaluation
19.3.1 Small Databases
19.3.2 Large Databases
19.4 Open Problems
19.5 Bibliographic Notes
Bibliography
Author Index
Subject Index
- Edition: 1
- Latest edition
- Published: May 1, 1997
- Language: English
CZ
Carlo Zaniolo
Carlo Zaniolo holds the Friedman Chair in Knowledge Sciences at the University of California, Los Angeles. He is an active resarcher in the areas of database, knowledge bases, and intelligent databases.
SC
Stefano Ceri
Stefano Ceri is Professor of Database Systems at Politecnico di Milano. His research interests are focused on extending database technology to incorporate data distribution, deductive and active rules, and object orientation.
CF
Christos Faloutsos
Christos Faloutsos is Associate Professor of Computer Science at the University of Maryland, College Park. His research interests include physical database design, searching methods for text, geographic information systems, and indexing methods for medical and multimedia databases.
RS
Richard T. Snodgrass
Richard T. Snodgrass is Professor of Computer Science at the University of Arizona, and co-director of the TimeCenter, an international center for the support of temporal database applications on traditional and emerging DBMS technologies. His resarch interests include temporal databases, query language design, query optimization and evaluation, storage structures, database design, and software development databases.
VS
V.S. Subrahmanian
V.S. Subrahmanian is Associate Professor of Computer Science at the University of Maryland, College Park, where his work focuses on incomplete and uncertain information in databases and knowledge bases, integrated heterogeneous data and software, and multimedia systems. V.S. Subrahmanian was awarded his Ph.D. in Computer Science from Syracuse University in 1989. He is an Associate Professor in the Computer Science Department at the University of Maryland, where he also heads the Multimedia Systems Laboratory. He is the recipient of the prestigious National Science Foundation Young Investigator Award, and the Distinguished Young Scientist Award from the Maryland Academy of Sciences. He has worked extensively in knowledge bases, synthesizing techniques in artificial intelligence, and database engineering. He is an editor of the IEEE Transactions on Knowledge and Data Engineering and AI Communications Journal, and co-author of Advanced Database Systems (1997 Morgan Kaufmann Publishers, Inc.).
Affiliations and expertise
University of Maryland, College Park.RZ
Roberto Zicari
Roberto Zicari is Professor of Computer Science at the Johann Wolfgang Goethe University in Frankfurt, and an internationally recognized expert in the field of object database systems.