Distributed database management system book pdf

HW IN Distributed Data Base

Principles of Distributed Database Systems

M. Tamer Özsu • Patrick Valduriez

Principles of Distributed Database Systems

Third Edition

All rights reserved. This work may not be translated or copied in whole or in part without the written permission of the publisher (Springer Science+Business Media, LLC, 233 Spring Street, New York, NY 10013, USA), except for brief excerpts in connection with reviews or scholarly analysis. Use in connection with any form of information storage and retrieval, electronic adaptation, computer, software, or by similar or dissimilar methodology now known or hereafter developed is forbidden. The use in this publication of trade names, trademarks, service marks, and similar terms, even if they are not identified as such, is not to be taken as an expression of opinion as to whether or not they are subject to proprietary rights.

Printed on acid-free paper

Springer is part of Springer Science+Business Media (www.springer.com)

Springer New York Dordrecht Heidelberg London

M. Tamer Özsu David R. Cheriton School of Computer Science University of Waterloo Waterloo Ontario Canada N2L 3G1

ISBN 978-1-4419-8833-1 e-ISBN 978-1-4419-8834-8 DOI 10.1007/978-1-4419-8834-8

This book was previously published by: Pearson Education, Inc.

Tamer.Ozsu@uwaterloo.ca

Library of Congress Control Number: 2011922491

© Springer Science+Business Media, LLC 2011

Patrick Valduriez

LIRMM

34392 Montpellier Cedex France Patrick.Valduriez@inria.fr

INRIA

161 rue Ada

To my family and my parents M.T.Ö.

To Esther, my daughters Anna, Juliette and Sarah, and my parents

P.V.

Preface

It has been almost twenty years since the first edition of this book appeared, and ten years since we released the second edition. As one can imagine, in a fast changing area such as this, there have been significant changes in the intervening period. Distributed data management went from a potentially significant technology to one that is common place. The advent of the Internet and the World Wide Web have certainly changed the way we typically look at distribution. The emergence in recent years of different forms of distributed computing, exemplified by data streams and cloud computing, has regenerated interest in distributed data management. Thus, it was time for a major revision of the material.

We started to work on this edition five years ago, and it has taken quite a while to complete the work. The end result, however, is a book that has been heavily revised – while we maintained and updated the core chapters, we have also added new ones. The major changes are the following:

1. Database integration and querying is now treated in much more detail, re- flecting the attention these topics have received in the community in the past decade. Chapter 4 focuses on the integration process, while Chapter 9 discusses querying over multidatabase systems.

2. The previous editions had only brief discussion of data replication protocols. This topic is now covered in a separate chapter (Chapter 13) where we provide an in-depth discussion of the protocols and how they can be integrated with transaction management.

3. Peer-to-peer data management is discussed in depth in Chapter 16. These systems have become an important and interesting architectural alternative to classical distributed database systems. Although the early distributed database systems architectures followed the peer-to-peer paradigm, the modern incar- nation of these systems have fundamentally different characteristics, so they deserve in-depth discussion in a chapter of their own.

4. Web data management is discussed in Chapter 17. This is a difficult topic to cover since there is no unifying framework. We discuss various aspects

vii

viii Preface

of the topic ranging from web models to search engines to distributed XML processing.

5. Earlier editions contained a chapter where we discussed “recent issues” at the time. In this edition, we again have a similar chapter (Chapter 18) where we cover stream data management and cloud computing. These topics are still in a flux and are subjects of considerable ongoing research. We highlight the issues and the potential research directions.

The resulting manuscript strikes a balance between our two objectives, namely to address new and emerging issues, and maintain the main characteristics of the book in addressing the principles of distributed data management.

The organization of the book can be divided into two major parts. The first part covers the fundamental principles of distributed data management and consist of Chapters 1 to 14. Chapter 2 in this part covers the background and can be skipped if the students already have sufficient knowledge of the relational database concepts and the computer network technology. The only part of this chapter that is essential is Example 2.3, which introduces the running example that we use throughout much of the book. The second part covers more advanced topics and includes Chapters 15 – 18. What one covers in a course depends very much on the duration and the course objectives. If the course aims to discuss the fundamental techniques, then it might cover Chapters 1, 3, 5, 6–8, 10–12. An extended coverage would include, in addition to the above, Chapters 4, 9, and 13. Courses that have time to cover more material can selectively pick one or more of Chapters 15 – 18 from the second part.

Many colleagues have assisted with this edition of the book. S. Keshav (Univer- sity of Waterloo) has read and provided many suggestions to update the sections on computer networks. Renée Miller (University of Toronto) and Erhard Rahm (University of Leipzig) read an early draft of Chapter 4 and provided many com- ments, Alon Halevy (Google) answered a number of questions about this chapter and provided a draft copy of his upcoming book on this topic as well as reading and providing feedback on Chapter 9, Avigdor Gal (Technion) also reviewed and critiqued this chapter very thoroughly. Matthias Jarke and Xiang Li (University of Aachen), Gottfried Vossen (University of Muenster), Erhard Rahm and Andreas Thor (University of Leipzig) contributed exercises to this chapter. Hubert Naacke (University of Paris 6) contributed to the section on heterogeneous cost modeling and Fabio Porto (LNCC, Petropolis) to the section on adaptive query processing of Chapter 9. Data replication (Chapter 13) could not have been written without the assistance of Gustavo Alonso (ETH Zürich) and Bettina Kemme (McGill University). Tamer spent four months in Spring 2006 visiting Gustavo where work on this chapter began and involved many long discussions. Bettina read multiple iterations of this chapter over the next one year criticizing everything and pointing out better ways of explaining the material. Esther Pacitti (University of Montpellier) also contributed to this chapter, both by reviewing it and by providing background material; she also contributed to the section on replication in database clusters in Chapter 14. Ricardo Jimenez-Peris also contributed to that chapter in the section on fault-tolerance in database clusters. Khuzaima Daudjee (University of Waterloo) read and provided

Preface ix

comments on this chapter as well. Chapter 15 on Distributed Object Database Man- agement was reviewed by Serge Abiteboul (INRIA), who provided important critique of the material and suggestions for its improvement. Peer-to-peer data management (Chapter 16) owes a lot to discussions with Beng Chin Ooi (National University of Singapore) during the four months Tamer was visiting NUS in the fall of 2006. The section of Chapter 16 on query processing in P2P systems uses material from the PhD work of Reza Akbarinia (INRIA) and Wenceslao Palma (PUC-Valparaiso, Chile) while the section on replication uses material from the PhD work of Vidal Martins (PUCPR, Curitiba). The distributed XML processing section of Chapter 17 uses material from the PhD work of Ning Zhang (Facebook) and Patrick Kling at the University of Waterloo, and Ying Zhang at CWI. All three of them also read the material and provided significant feedback. Victor Muntés i Mulero (Universitat Politècnica de Catalunya) contributed to the exercises in that chapter. Özgür Ulusoy (Bilkent University) provided comments and corrections on Chapters 16 and 17. Data stream management section of Chapter 18 draws from the PhD work of Lukasz Golab (AT&T Labs-Research), and Yingying Tao at the University of Waterloo. Walid Aref (Purdue University) and Avigdor Gal (Technion) used the draft of the book in their courses, which was very helpful in debugging certain parts. We thank them, as well as many colleagues who had helped out with the first two editions, for all their assistance. We have not always followed their advice, and, needless to say, the resulting problems and errors are ours. Students in two courses at the University of Waterloo (Web Data Management in Winter 2005, and Internet-Scale Data Distribution in Fall 2005) wrote surveys as part of their coursework that were very helpful in structuring some chapters. Tamer taught courses at ETH Zürich (PDDBS – Parallel and Distributed Databases in Spring 2006) and at NUS (CS5225 – Parallel and Distributed Database Systems in Fall 2010) using parts of this edition. We thank students in all these courses for their contributions and their patience as they had to deal with chapters that were works-in-progress – the material got cleaned considerably as a result of these teaching experiences.

You will note that the publisher of the third edition of the book is different than the first two editions. Pearson, our previous publisher, decided not to be involved with the third edition. Springer subsequently showed considerable interest in the book. We would like to thank Susan Lagerstrom-Fife and Jennifer Evans of Springer for their lightning-fast decision to publish the book, and Jennifer Mauer for a ton of hand-holding during the conversion process. We would also like to thank Tracy Dunkelberger of Pearson who shepherded the reversal of the copyright to us without delay.

As in earlier editions, we will have presentation slides that can be used to teach from the book as well as solutions to most of the exercises. These will be available from Springer to instructors who adopt the book and there will be a link to them from the book’s site at springer.com.

Finally, we would be very interested to hear your comments and suggestions regarding the material. We welcome any feedback, but we would particularly like to receive feedback on the following aspects:

x Preface

1. any errors that may have remained despite our best efforts (although we hope there are not many);

2. any topics that should no longer be included and any topics that should be added or expanded; and

3. any exercises that you may have designed that you would like to be included in the book.

M. Tamer Özsu (Tamer.Ozsu@uwaterloo.ca) Patrick Valduriez (Patrick.Valduriez@inria.fr)

November 2010

Contents

1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.1 Distributed Data Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 2 1.2 What is a Distributed Database System? . . . . . . . . . . . . . . . . . . . . . . . 3 1.3 Data Delivery Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5 1.4 Promises of DDBSs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 7

1.4.1 Transparent Management of Distributed and Replicated Data 7 1.4.2 Reliability Through Distributed Transactions . . . . . . . . . . . . . 12 1.4.3 Improved Performance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14 1.4.4 Easier System Expansion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15

1.5 Complications Introduced by Distribution . . . . . . . . . . . . . . . . . . . . . . 16 1.6 Design Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

1.6.1 Distributed Database Design . . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.6.2 Distributed Directory Management . . . . . . . . . . . . . . . . . . . . . 17 1.6.3 Distributed Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . 17 1.6.4 Distributed Concurrency Control . . . . . . . . . . . . . . . . . . . . . . . 18 1.6.5 Distributed Deadlock Management . . . . . . . . . . . . . . . . . . . . . 18 1.6.6 Reliability of Distributed DBMS . . . . . . . . . . . . . . . . . . . . . . . 18 1.6.7 Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.6.8 Relationship among Problems . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.6.9 Additional Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 20

1.7 Distributed DBMS Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.7.1 ANSI/SPARC Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . 21 1.7.2 A Generic Centralized DBMS Architecture . . . . . . . . . . . . . . 23 1.7.3 Architectural Models for Distributed DBMSs . . . . . . . . . . . . . 25 1.7.4 Autonomy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 1.7.5 Distribution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.7.6 Heterogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27 1.7.7 Architectural Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.7.8 Client/Server Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 28 1.7.9 Peer-to-Peer Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 1.7.10 Multidatabase System Architecture . . . . . . . . . . . . . . . . . . . . . 35

xi

xii Contents

1.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

2 Background . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1 Overview of Relational DBMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

2.1.1 Relational Database Concepts . . . . . . . . . . . . . . . . . . . . . . . . . . 41 2.1.2 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 43 2.1.3 Relational Data Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . 45

2.2 Review of Computer Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 2.2.1 Types of Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 60 2.2.2 Communication Schemes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 63 2.2.3 Data Communication Concepts . . . . . . . . . . . . . . . . . . . . . . . . 65 2.2.4 Communication Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67

2.3 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70

3 Distributed Database Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71 3.1 Top-Down Design Process . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 3.2 Distribution Design Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75

3.2.1 Reasons for Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 75 3.2.2 Fragmentation Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . 76 3.2.3 Degree of Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77 3.2.4 Correctness Rules of Fragmentation . . . . . . . . . . . . . . . . . . . . . 79 3.2.5 Allocation Alternatives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 79 3.2.6 Information Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 80

3.3 Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.3.1 Horizontal Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81 3.3.2 Vertical Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 3.3.3 Hybrid Fragmentation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112

3.4 Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 113 3.4.1 Allocation Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 114 3.4.2 Information Requirements . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 116 3.4.3 Allocation Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118 3.4.4 Solution Methods . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 121

3.5 Data Directory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 122 3.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 123 3.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

4 Database Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 4.1 Bottom-Up Design Methodology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 4.2 Schema Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 137

4.2.1 Schema Heterogeneity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140 4.2.2 Linguistic Matching Approaches . . . . . . . . . . . . . . . . . . . . . . . 141 4.2.3 Constraint-based Matching Approaches . . . . . . . . . . . . . . . . . 143 4.2.4 Learning-based Matching . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 145 4.2.5 Combined Matching Approaches . . . . . . . . . . . . . . . . . . . . . . . 146

4.3 Schema Integration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 147

Contents xiii

4.4 Schema Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 149 4.4.1 Mapping Creation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 150 4.4.2 Mapping Maintenance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155

4.5 Data Cleaning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 157 4.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 159 4.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 160

5 Data and Access Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 171 5.1 View Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 172

5.1.1 Views in Centralized DBMSs . . . . . . . . . . . . . . . . . . . . . . . . . . 172 5.1.2 Views in Distributed DBMSs . . . . . . . . . . . . . . . . . . . . . . . . . . 175 5.1.3 Maintenance of Materialized Views . . . . . . . . . . . . . . . . . . . . . 177

5.2 Data Security . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 180 5.2.1 Discretionary Access Control . . . . . . . . . . . . . . . . . . . . . . . . . . 181 5.2.2 Multilevel Access Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 183 5.2.3 Distributed Access Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . 185

5.3 Semantic Integrity Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 187 5.3.1 Centralized Semantic Integrity Control . . . . . . . . . . . . . . . . . . 189 5.3.2 Distributed Semantic Integrity Control . . . . . . . . . . . . . . . . . . 194

5.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 200 5.5 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 201

6 Overview of Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 205 6.1 Query Processing Problem . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 206 6.2 Objectives of Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 209 6.3 Complexity of Relational Algebra Operations . . . . . . . . . . . . . . . . . . . 210 6.4 Characterization of Query Processors . . . . . . . . . . . . . . . . . . . . . . . . . . 211

6.4.1 Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 6.4.2 Types of Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 6.4.3 Optimization Timing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 6.4.4 Statistics . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 213 6.4.5 Decision Sites . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 214 6.4.6 Exploitation of the Network Topology . . . . . . . . . . . . . . . . . . . 214 6.4.7 Exploitation of Replicated Fragments . . . . . . . . . . . . . . . . . . . 215 6.4.8 Use of Semijoins . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215

6.5 Layers of Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 215 6.5.1 Query Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 216 6.5.2 Data Localization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 217 6.5.3 Global Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 218 6.5.4 Distributed Query Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . 219

6.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 219 6.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 220

xiv Contents

7 Query Decomposition and Data Localization . . . . . . . . . . . . . . . . . . . . . . 221 7.1 Query Decomposition . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222

7.1.1 Normalization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 222 7.1.2 Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 223 7.1.3 Elimination of Redundancy . . . . . . . . . . . . . . . . . . . . . . . . . . . . 226 7.1.4 Rewriting . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 227

7.2 Localization of Distributed Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 231 7.2.1 Reduction for Primary Horizontal Fragmentation . . . . . . . . . . 232 7.2.2 Reduction for Vertical Fragmentation . . . . . . . . . . . . . . . . . . . 235 7.2.3 Reduction for Derived Fragmentation . . . . . . . . . . . . . . . . . . . 237 7.2.4 Reduction for Hybrid Fragmentation . . . . . . . . . . . . . . . . . . . . 238

7.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241 7.4 Bibliographic NOTES . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 241

8 Optimization of Distributed Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 245 8.1 Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246

8.1.1 Search Space . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 246 8.1.2 Search Strategy . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 248 8.1.3 Distributed Cost Model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249

8.2 Centralized Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 257 8.2.1 Dynamic Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . 257 8.2.2 Static Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 261 8.2.3 Hybrid Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 265

8.3 Join Ordering in Distributed Queries . . . . . . . . . . . . . . . . . . . . . . . . . . 267 8.3.1 Join Ordering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 267 8.3.2 Semijoin Based Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . . . 269 8.3.3 Join versus Semijoin . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 272

8.4 Distributed Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273 8.4.1 Dynamic Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 274 8.4.2 Static Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 277 8.4.3 Semijoin-based Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 281 8.4.4 Hybrid Approach . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 286

8.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 290 8.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 292

9 Multidatabase Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 297 9.1 Issues in Multidatabase Query Processing . . . . . . . . . . . . . . . . . . . . . . 298 9.2 Multidatabase Query Processing Architecture . . . . . . . . . . . . . . . . . . . 299 9.3 Query Rewriting Using Views . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301

9.3.1 Datalog Terminology . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 301 9.3.2 Rewriting in GAV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 302 9.3.3 Rewriting in LAV . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304

9.4 Query Optimization and Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . 307 9.4.1 Heterogeneous Cost Modeling . . . . . . . . . . . . . . . . . . . . . . . . . 307 9.4.2 Heterogeneous Query Optimization . . . . . . . . . . . . . . . . . . . . . 314

Contents xv

9.4.3 Adaptive Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . 320 9.5 Query Translation and Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 327 9.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 330 9.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 331

10 Introduction to Transaction Management . . . . . . . . . . . . . . . . . . . . . . . . . 335 10.1 Definition of a Transaction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 337

10.1.1 Termination Conditions of Transactions . . . . . . . . . . . . . . . . . 339 10.1.2 Characterization of Transactions . . . . . . . . . . . . . . . . . . . . . . . 340 10.1.3 Formalization of the Transaction Concept . . . . . . . . . . . . . . . . 341

10.2 Properties of Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 10.2.1 Atomicity . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 344 10.2.2 Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 345 10.2.3 Isolation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 346 10.2.4 Durability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349

10.3 Types of Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 349 10.3.1 Flat Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 351 10.3.2 Nested Transactions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 352 10.3.3 Workflows . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 353

10.4 Architecture Revisited . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 356 10.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 357 10.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 358

11 Distributed Concurrency Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 361 11.1 Serializability Theory . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 362 11.2 Taxonomy of Concurrency Control Mechanisms . . . . . . . . . . . . . . . . . 367 11.3 Locking-Based Concurrency Control Algorithms . . . . . . . . . . . . . . . . 369

11.3.1 Centralized 2PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373 11.3.2 Distributed 2PL . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 374

11.4 Timestamp-Based Concurrency Control Algorithms . . . . . . . . . . . . . . 377 11.4.1 Basic TO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 378 11.4.2 Conservative TO Algorithm . . . . . . . . . . . . . . . . . . . . . . . . . . . 381 11.4.3 Multiversion TO Algorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . 383

11.5 Optimistic Concurrency Control Algorithms . . . . . . . . . . . . . . . . . . . . 384 11.6 Deadlock Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 387

11.6.1 Deadlock Prevention . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 389 11.6.2 Deadlock Avoidance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 390 11.6.3 Deadlock Detection and Resolution . . . . . . . . . . . . . . . . . . . . . 391

11.7 “Relaxed” Concurrency Control . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394 11.7.1 Non-Serializable Histories . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 395 11.7.2 Nested Distributed Transactions . . . . . . . . . . . . . . . . . . . . . . . . 396

11.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 398 11.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 401

xvi Contents

12 Distributed DBMS Reliability . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 405 12.1 Reliability Concepts and Measures . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406

12.1.1 System, State, and Failure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 406 12.1.2 Reliability and Availability . . . . . . . . . . . . . . . . . . . . . . . . . . . . 408 12.1.3 Mean Time between Failures/Mean Time to Repair . . . . . . . . 409

12.2 Failures in Distributed DBMS . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 410 12.2.1 Transaction Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 12.2.2 Site (System) Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 411 12.2.3 Media Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412 12.2.4 Communication Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 412

12.3 Local Reliability Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 12.3.1 Architectural Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . 413 12.3.2 Recovery Information . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 416 12.3.3 Execution of LRM Commands . . . . . . . . . . . . . . . . . . . . . . . . . 420 12.3.4 Checkpointing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 425 12.3.5 Handling Media Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 426

12.4 Distributed Reliability Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 427 12.4.1 Components of Distributed Reliability Protocols . . . . . . . . . . 428 12.4.2 Two-Phase Commit Protocol . . . . . . . . . . . . . . . . . . . . . . . . . . . 428 12.4.3 Variations of 2PC . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434

12.5 Dealing with Site Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 436 12.5.1 Termination and Recovery Protocols for 2PC . . . . . . . . . . . . . 437 12.5.2 Three-Phase Commit Protocol . . . . . . . . . . . . . . . . . . . . . . . . . 443

12.6 Network Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 448 12.6.1 Centralized Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450 12.6.2 Voting-based Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 450

12.7 Architectural Considerations . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 453 12.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 454 12.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 455

13 Data Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 459 13.1 Consistency of Replicated Databases . . . . . . . . . . . . . . . . . . . . . . . . . . 461

13.1.1 Mutual Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 461 13.1.2 Mutual Consistency versus Transaction Consistency . . . . . . . 463

13.2 Update Management Strategies . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 13.2.1 Eager Update Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 465 13.2.2 Lazy Update Propagation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 13.2.3 Centralized Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 466 13.2.4 Distributed Techniques . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 467

13.3 Replication Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 13.3.1 Eager Centralized Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . 468 13.3.2 Eager Distributed Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474 13.3.3 Lazy Centralized Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475 13.3.4 Lazy Distributed Protocols . . . . . . . . . . . . . . . . . . . . . . . . . . . . 480

13.4 Group Communication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 482

Contents xvii

13.5 Replication and Failures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 485 13.5.1 Failures and Lazy Replication . . . . . . . . . . . . . . . . . . . . . . . . . . 485 13.5.2 Failures and Eager Replication . . . . . . . . . . . . . . . . . . . . . . . . . 486

13.6 Replication Mediator Service . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 489 13.7 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 491 13.8 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 493

14 Parallel Database Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 497 14.1 Parallel Database System Architectures . . . . . . . . . . . . . . . . . . . . . . . . 498

14.1.1 Objectives . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 498 14.1.2 Functional Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 501 14.1.3 Parallel DBMS Architectures . . . . . . . . . . . . . . . . . . . . . . . . . . 502

14.2 Parallel Data Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 508 14.3 Parallel Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 512

14.3.1 Query Parallelism . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 513 14.3.2 Parallel Algorithms for Data Processing . . . . . . . . . . . . . . . . . 515 14.3.3 Parallel Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . 521

14.4 Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 525 14.4.1 Parallel Execution Problems . . . . . . . . . . . . . . . . . . . . . . . . . . . 525 14.4.2 Intra-Operator Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . 527 14.4.3 Inter-Operator Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . 529 14.4.4 Intra-Query Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . 530

14.5 Database Clusters . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 534 14.5.1 Database Cluster Architecture . . . . . . . . . . . . . . . . . . . . . . . . . . 535 14.5.2 Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 537 14.5.3 Load Balancing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 540 14.5.4 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 542 14.5.5 Fault-tolerance . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 545

14.6 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 546 14.7 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 547

15 Distributed Object Database Management . . . . . . . . . . . . . . . . . . . . . . . . 551 15.1 Fundamental Object Concepts and Object Models . . . . . . . . . . . . . . . 553

15.1.1 Object . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 553 15.1.2 Types and Classes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 556 15.1.3 Composition (Aggregation) . . . . . . . . . . . . . . . . . . . . . . . . . . . . 557 15.1.4 Subclassing and Inheritance . . . . . . . . . . . . . . . . . . . . . . . . . . . 558

15.2 Object Distribution Design . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 560 15.2.1 Horizontal Class Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . 561 15.2.2 Vertical Class Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563 15.2.3 Path Partitioning . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 563 15.2.4 Class Partitioning Algorithms . . . . . . . . . . . . . . . . . . . . . . . . . . 564 15.2.5 Allocation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565 15.2.6 Replication . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 565

15.3 Architectural Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 566

xviii Contents

15.3.1 Alternative Client/Server Architectures . . . . . . . . . . . . . . . . . . 567 15.3.2 Cache Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 572

15.4 Object Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 574 15.4.1 Object Identifier Management . . . . . . . . . . . . . . . . . . . . . . . . . . 574 15.4.2 Pointer Swizzling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 576 15.4.3 Object Migration . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 577

15.5 Distributed Object Storage . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 578 15.6 Object Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 582

15.6.1 Object Query Processor Architectures . . . . . . . . . . . . . . . . . . . 583 15.6.2 Query Processing Issues . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 584 15.6.3 Query Execution . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 589

15.7 Transaction Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 593 15.7.1 Correctness Criteria . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 594 15.7.2 Transaction Models and Object Structures . . . . . . . . . . . . . . . 596 15.7.3 Transactions Management in Object DBMSs . . . . . . . . . . . . . 596 15.7.4 Transactions as Objects . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 605

15.8 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 606 15.9 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 607

16 Peer-to-Peer Data Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 611 16.1 Infrastructure . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614

16.1.1 Unstructured P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . 615 16.1.2 Structured P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 618 16.1.3 Super-peer P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 622 16.1.4 Comparison of P2P Networks . . . . . . . . . . . . . . . . . . . . . . . . . . 624

16.2 Schema Mapping in P2P Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 624 16.2.1 Pairwise Schema Mapping . . . . . . . . . . . . . . . . . . . . . . . . . . . . 625 16.2.2 Mapping based on Machine Learning Techniques . . . . . . . . . 626 16.2.3 Common Agreement Mapping . . . . . . . . . . . . . . . . . . . . . . . . . 626 16.2.4 Schema Mapping using IR Techniques . . . . . . . . . . . . . . . . . . 627

16.3 Querying Over P2P Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628 16.3.1 Top-k Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 628 16.3.2 Join Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 640 16.3.3 Range Queries . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 642

16.4 Replica Consistency . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 645 16.4.1 Basic Support in DHTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 646 16.4.2 Data Currency in DHTs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 648 16.4.3 Replica Reconciliation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 649

16.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653 16.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 653

17 Web Data Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657 17.1 Web Graph Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 658

17.1.1 Compressing Web Graphs . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 660 17.1.2 Storing Web Graphs as S-Nodes . . . . . . . . . . . . . . . . . . . . . . . . 661

Contents xix

17.2 Web Search . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 663 17.2.1 Web Crawling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 664 17.2.2 Indexing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667 17.2.3 Ranking and Link Analysis . . . . . . . . . . . . . . . . . . . . . . . . . . . . 668 17.2.4 Evaluation of Keyword Search . . . . . . . . . . . . . . . . . . . . . . . . . 669

17.3 Web Querying . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 670 17.3.1 Semistructured Data Approach . . . . . . . . . . . . . . . . . . . . . . . . . 671 17.3.2 Web Query Language Approach . . . . . . . . . . . . . . . . . . . . . . . . 676 17.3.3 Question Answering . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 681 17.3.4 Searching and Querying the Hidden Web . . . . . . . . . . . . . . . . 685

17.4 Distributed XML Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 689 17.4.1 Overview of XML . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 691 17.4.2 XML Query Processing Techniques . . . . . . . . . . . . . . . . . . . . . 699 17.4.3 Fragmenting XML Data . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 703 17.4.4 Optimizing Distributed XML Processing . . . . . . . . . . . . . . . . 710

17.5 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 718 17.6 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 719

18 . . . . . . . . . . . . 723 18.1 Data Stream Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 723

18.1.1 Stream Data Models . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 725 18.1.2 Stream Query Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 727 18.1.3 Streaming Operators and their Implementation . . . . . . . . . . . . 732 18.1.4 Query Processing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 734 18.1.5 DSMS Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . 738 18.1.6 Load Shedding and Approximation . . . . . . . . . . . . . . . . . . . . . 739 18.1.7 Multi-Query Optimization . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 740 18.1.8 Stream Mining . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 741

18.2 Cloud Data Management . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 744 18.2.1 Taxonomy of Clouds . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 745 18.2.2 Grid Computing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 748 18.2.3 Cloud architectures . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 751 18.2.4 Data management in the cloud . . . . . . . . . . . . . . . . . . . . . . . . . 753

18.3 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 760 18.4 Bibliographic Notes . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 762

References . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 765

Index . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 833

Current Issues: Streaming Data and Cloud Computing

Chapter 1 Introduction

Distributed database system (DDBS) technology is the union of what appear to be two diametrically opposed approaches to data processing: database system and computer network technologies. Database systems have taken us from a paradigm of data processing in which each application defined and maintained its own data (Figure 1.1) to one in which the data are defined and administered centrally (Figure 1.2). This new orientation results in data independence, whereby the application programs are immune to changes in the logical or physical organization of the data, and vice versa.

One of the major motivations behind the use of database systems is the desire to integrate the operational data of an enterprise and to provide centralized, thus controlled access to that data. The technology of computer networks, on the other hand, promotes a mode of work that goes against all centralization efforts. At first glance it might be difficult to understand how these two contrasting approaches can possibly be synthesized to produce a technology that is more powerful and more promising than either one alone. The key to this understanding is the realization

PROGRAM 1

Data

Description

PROGRAM 2

FILE 1

FILE 2

FILE 3 PROGRAM 3

Data

Description

Data

Description

R E

D U

N D

A N

T D

A T A

Fig. 1.1 Traditional File Processing

1 DOI 10.1007/978-1-4419-8834-8_1, © Springer Science+Business Media, LLC 2011 M.T. Özsu and P. Valduriez, Principles of Distributed Database Systems: Third Edition,

2 1 Introduction

...

Data Description

Data Manipulation DATABASE

PROGRAM 1

PROGRAM 2

PROGRAM 3

Fig. 1.2 Database Processing

that the most important objective of the database technology is integration, not centralization. It is important to realize that either one of these terms does not necessarily imply the other. It is possible to achieve integration without centralization, and that is exactly what the distributed database technology attempts to achieve.

In this chapter we define the fundamental concepts and set the framework for discussing distributed databases. We start by examining distributed systems in general in order to clarify the role of database technology within distributed data processing, and then move on to topics that are more directly related to DDBS.

1.1 Distributed Data Processing

The term distributed processing (or distributed computing) is hard to define precisely. Obviously, some degree of distributed processing goes on in any computer system, even on single-processor computers where the central processing unit (CPU) and in- put/output (I/O) functions are separated and overlapped. This separation and overlap can be considered as one form of distributed processing. The widespread emergence of parallel computers has further complicated the picture, since the distinction be- tween distributed computing systems and some forms of parallel computers is rather vague.

In this book we define distributed processing in such a way that it leads to a definition of a distributed database system. The working definition we use for a distributed computing system states that it is a number of autonomous processing elements (not necessarily homogeneous) that are interconnected by a computer network and that cooperate in performing their assigned tasks. The “processing element” referred to in this definition is a computing device that can execute a program on its own. This definition is similar to those given in distributed systems textbooks (e.g., [Tanenbaum and van Steen, 2002] and [Colouris et al., 2001]).

A fundamental question that needs to be asked is: What is being distributed? One of the things that might be distributed is the processing logic. In fact, the definition of a distributed computing system given above implicitly assumes that the

1.2 What is a Distributed Database System? 3

processing logic or processing elements are distributed. Another possible distribution is according to function. Various functions of a computer system could be delegated to various pieces of hardware or software. A third possible mode of distribution is according to data. Data used by a number of applications may be distributed to a number of processing sites. Finally, control can be distributed. The control of the execution of various tasks might be distributed instead of being performed by one computer system. From the viewpoint of distributed database systems, these modes of distribution are all necessary and important. In the following sections we talk about these in more detail.

Another reasonable question to ask at this point is: Why do we distribute at all? The classical answers to this question indicate that distributed processing better corresponds to the organizational structure of today’s widely distributed enterprises, and that such a system is more reliable and more responsive. More importantly, many of the current applications of computer technology are inherently distributed. Web-based applications, electronic commerce business over the Internet, multimedia applications such as news-on-demand or medical imaging, manufacturing control systems are all examples of such applications.

From a more global perspective, however, it can be stated that the fundamental reason behind distributed processing is to be better able to cope with the large-scale data management problems that we face today, by using a variation of the well-known divide-and-conquer rule. If the necessary software support for distributed processing can be developed, it might be possible to solve these complicated problems simply by dividing them into smaller pieces and assigning them to different software groups, which work on different computers and produce a system that runs on multiple processing elements but can work efficiently toward the execution of a common task.

Distributed database systems should also be viewed within this framework and treated as tools that could make distributed processing easier and more efficient. It is reasonable to draw an analogy between what distributed databases might offer to the data processing world and what the database technology has already provided. There is no doubt that the development of general-purpose, adaptable, efficient distributed database systems has aided greatly in the task of developing distributed software.

1.2 What is a Distributed Database System?

We define a distributed database as a collection of multiple, logically interrelated databases distributed over a computer network. A distributed database management system (distributed DBMS) is then defined as the software system that permits the management of the distributed database and makes the distribution transparent to the users. Sometimes “distributed database system” (DDBS) is used to refer jointly to the distributed database and the distributed DBMS. The two important terms in these definitions are “logically interrelated” and “distributed over a computer network.” They help eliminate certain cases that have sometimes been accepted to represent a DDBS.

4 1 Introduction

A DDBS is not a “collection of files” that can be individually stored at each node of a computer network. To form a DDBS, files should not only be logically related, but there should be structured among the files, and access should be via a common interface. We should note that there has been much recent activity in providing DBMS functionality over semi-structured data that are stored in files on the Internet (such as Web pages). In light of this activity, the above requirement may seem unnecessarily strict. Nevertheless, it is important to make a distinction between a DDBS where this requirement is met, and more general distributed data management systems that provide a “DBMS-like” access to data. In various chapters of this book, we will expand our discussion to cover these more general systems.

It has sometimes been assumed that the physical distribution of data is not the most significant issue. The proponents of this view would therefore feel comfortable in labeling as a distributed database a number of (related) databases that reside in the same computer system. However, the physical distribution of data is important. It creates problems that are not encountered when the databases reside in the same com- puter. These difficulties are discussed in Section 1.5. Note that physical distribution does not necessarily imply that the computer systems be geographically far apart; they could actually be in the same room. It simply implies that the communication between them is done over a network instead of through shared memory or shared disk (as would be the case with multiprocessor systems), with the network as the only shared resource.

This suggests that multiprocessor systems should not be considered as DDBSs. Although shared-nothing multiprocessors, where each processor node has its own primary and secondary memory, and may also have its own peripherals, are quite similar to the distributed environment that we focus on, there are differences. The fundamental difference is the mode of operation. A multiprocessor system design is rather symmetrical, consisting of a number of identical processor and memory components, and controlled by one or more copies of the same operating system that is responsible for a strict control of the task assignment to each processor. This is not true in distributed computing systems, where heterogeneity of the operating system as well as the hardware is quite common. Database systems that run over multiprocessor systems are called parallel database systems and are discussed in Chapter 14.

A DDBS is also not a system where, despite the existence of a network, the database resides at only one node of the network (Figure 1.3). In this case, the problems of database management are no different than the problems encountered in a centralized database environment (shortly, we will discuss client/server DBMSs which relax this requirement to a certain extent). The database is centrally managed by one computer system (site 2 in Figure 1.3) and all the requests are routed to that site. The only additional consideration has to do with transmission delays. It is obvious that the existence of a computer network or a collection of “files” is not sufficient to form a distributed database system. What we are interested in is an environment where data are distributed among a number of sites (Figure 1.4).

1.3 Data Delivery Alternatives 5

Site 1

Site 2

Site 3Site 4

Site 5

Communication Network

Fig. 1.3 Central Database on a Network

Site 1

Site 2

Site 3Site 4

Site 5

Communication Network

Fig. 1.4 DDBS Environment

1.3 Data Delivery Alternatives

In distributed databases, data are “delivered” from the sites where they are stored to where the query is posed. We characterize the data delivery alternatives along three orthogonal dimensions: delivery modes, frequency and communication methods. The combinations of alternatives along each of these dimensions (that we discuss next) provide a rich design space.

The alternative delivery modes are pull-only, push-only and hybrid. In the pull- only mode of data delivery, the transfer of data from servers to clients is initiated by a client pull. When a client request is received at a server, the server responds by locating the requested information. The main characteristic of pull-based delivery is that the arrival of new data items or updates to existing data items are carried out at a

6 1 Introduction

server without notification to clients unless clients explicitly poll the server. Also, in pull-based mode, servers must be interrupted continuously to deal with requests from clients. Furthermore, the information that clients can obtain from a server is limited to when and what clients know to ask for. Conventional DBMSs offer primarily pull-based data delivery.

In the push-only mode of data delivery, the transfer of data from servers to clients is initiated by a server push in the absence of any specific request from clients. The main difficulty of the push-based approach is in deciding which data would be of common interest, and when to send them to clients – alternatives are periodic, irregular, or conditional. Thus, the usefulness of server push depends heavily upon the accuracy of a server to predict the needs of clients. In push-based mode, servers disseminate information to either an unbounded set of clients (random broadcast) who can listen to a medium or selective set of clients (multicast), who belong to some categories of recipients that may receive the data.

The hybrid mode of data delivery combines the client-pull and server-push mech- anisms. The continuous (or continual) query approach (e.g., [Liu et al., 1996],[Terry et al., 1992],[Chen et al., 2000],[Pandey et al., 2003]) presents one possible way of combining the pull and push modes: namely, the transfer of information from servers to clients is first initiated by a client pull (by posing the query), and the subsequent transfer of updated information to clients is initiated by a server push.

There are three typical frequency measurements that can be used to classify the regularity of data delivery. They are periodic, conditional, and ad-hoc or irregular.

In periodic delivery, data are sent from the server to clients at regular intervals. The intervals can be defined by system default or by clients using their profiles. Both pull and push can be performed in periodic fashion. Periodic delivery is carried out on a regular and pre-specified repeating schedule. A client request for IBM’s stock price every week is an example of a periodic pull. An example of periodic push is when an application can send out stock price listing on a regular basis, say every morning. Periodic push is particularly useful for situations in which clients might not be available at all times, or might be unable to react to what has been sent, such as in the mobile setting where clients can become disconnected.

In conditional delivery, data are sent from servers whenever certain conditions installed by clients in their profiles are satisfied. Such conditions can be as simple as a given time span or as complicated as event-condition-action rules. Conditional delivery is mostly used in the hybrid or push-only delivery systems. Using condi- tional push, data are sent out according to a pre-specified condition, rather than any particular repeating schedule. An application that sends out stock prices only when they change is an example of conditional push. An application that sends out a balance statement only when the total balance is 5% below the pre-defined balance threshold is an example of hybrid conditional push. Conditional push assumes that changes are critical to the clients, and that clients are always listening and need to respond to what is being sent. Hybrid conditional push further assumes that missing some update information is not crucial to the clients.

Ad-hoc delivery is irregular and is performed mostly in a pure pull-based system. Data are pulled from servers to clients in an ad-hoc fashion whenever clients request

1.4 Promises of DDBSs 7

it. In contrast, periodic pull arises when a client uses polling to obtain data from servers based on a regular period (schedule).

The third component of the design space of information delivery alternatives is the communication method. These methods determine the various ways in which servers and clients communicate for delivering information to clients. The alternatives are unicast and one-to-many. In unicast, the communication from a server to a client is one-to-one: the server sends data to one client using a particular delivery mode with some frequency. In one-to-many, as the name implies, the server sends data to a number of clients. Note that we are not referring here to a specific protocol; one-to-many communication may use a multicast or broadcast protocol.

We should note that this characterization is subject to considerable debate. It is not clear that every point in the design space is meaningful. Furthermore, specifi- cation of alternatives such as conditional and periodic (which may make sense) is difficult. However, it serves as a first-order characterization of the complexity of emerging distributed data management systems. For the most part, in this book, we are concerned with pull-only, ad hoc data delivery systems, although examples of other approaches are discussed in some chapters.

1.4 Promises of DDBSs

Many advantages of DDBSs have been cited in literature, ranging from sociological reasons for decentralization [D’Oliviera, 1977] to better economics. All of these can be distilled to four fundamentals which may also be viewed as promises of DDBS technology: transparent management of distributed and replicated data, reliable access to data through distributed transactions, improved performance, and easier system expansion. In this section we discuss these promises and, in the process, introduce many of the concepts that we will study in subsequent chapters.

1.4.1 Transparent Management of Distributed and Replicated Data

Transparency refers to separation of the higher-level semantics of a system from lower-level implementation issues. In other words, a transparent system “hides” the implementation details from users. The advantage of a fully transparent DBMS is the high level of support that it provides for the development of complex applications. It is obvious that we would like to make all DBMSs (centralized or distributed) fully transparent.

Let us start our discussion with an example. Consider an engineering firm that has offices in Boston, Waterloo, Paris and San Francisco. They run projects at each of these sites and would like to maintain a database of their employees, the projects and other related data. Assuming that the database is relational, we can store

8 1 Introduction

this information in two relations: EMP(ENO, ENAME, TITLE)1 and PROJ(PNO, PNAME, BUDGET). We also introduce a third relation to store salary information: SAL(TITLE, AMT) and a fourth relation ASG which indicates which employees have been assigned to which projects for what duration with what responsibility: ASG(ENO, PNO, RESP, DUR). If all of this data were stored in a centralized DBMS, and we wanted to find out the names and employees who worked on a project for more than 12 months, we would specify this using the following SQL query:

SELECT ENAME, AMT FROM EMP, ASG, SAL WHERE ASG.DUR > 12 AND EMP.ENO = ASG.ENO AND SAL.TITLE = EMP.TITLE

However, given the distributed nature of this firm’s business, it is preferable, under these circumstances, to localize data such that data about the employees in Waterloo office are stored in Waterloo, those in the Boston office are stored in Boston, and so forth. The same applies to the project and salary information. Thus, what we are engaged in is a process where we partition each of the relations and store each partition at a different site. This is known as fragmentation and we discuss it further below and in detail in Chapter 3.

Furthermore, it may be preferable to duplicate some of this data at other sites for performance and reliability reasons. The result is a distributed database which is fragmented and replicated (Figure 1.5). Fully transparent access means that the users can still pose the query as specified above, without paying any attention to the fragmentation, location, or replication of data, and let the system worry about resolving these issues.

For a system to adequately deal with this type of query over a distributed, frag- mented and replicated database, it needs to be able to deal with a number of different types of transparencies. We discuss these in this section.

1.4.1.1 Data Independence

Data independence is a fundamental form of transparency that we look for within a DBMS. It is also the only type that is important within the context of a centralized DBMS. It refers to the immunity of user applications to changes in the definition and organization of data, and vice versa.

As is well-known, data definition occurs at two levels. At one level the logical structure of the data are specified, and at the other level its physical structure. The former is commonly known as the schema definition, whereas the latter is referred to as the physical data description. We can therefore talk about two types of data

1 We discuss relational systems in Chapter 2 (Section 2.1) where we develop this example further. For the time being, it is sufficient to note that this nomenclature indicates that we have just defined a relation with three attributes: ENO (which is the key, identified by underlining), ENAME and TITLE.

1.4 Promises of DDBSs 9

Paris

San

FranciscoWaterloo

Boston

Communication

Network

Boston employees, Paris employees,

Boston projects

Waterloo employees,

Waterloo projects, Paris projects

San Francisco employees,

San Francisco projects

Paris employees, Boston employees,

Paris projects, Boston projects

Fig. 1.5 A Distributed Application

independence: logical data independence and physical data independence. Logical data independence refers to the immunity of user applications to changes in the logical structure (i.e., schema) of the database. Physical data independence, on the other hand, deals with hiding the details of the storage structure from user applications. When a user application is written, it should not be concerned with the details of physical data organization. Therefore, the user application should not need to be modified when data organization changes occur due to performance considerations.

1.4.1.2 Network Transparency

In centralized database systems, the only available resource that needs to be shielded from the user is the data (i.e., the storage system). In a distributed database envi- ronment, however, there is a second resource that needs to be managed in much the same manner: the network. Preferably, the user should be protected from the operational details of the network; possibly even hiding the existence of the network. Then there would be no difference between database applications that would run on a centralized database and those that would run on a distributed database. This type of transparency is referred to as network transparency or distribution transparency.

One can consider network transparency from the viewpoint of either the services provided or the data. From the former perspective, it is desirable to have a uniform means by which services are accessed. From a DBMS perspective, distribution transparency requires that users do not have to specify where data are located.

Sometimes two types of distribution transparency are identified: location trans- parency and naming transparency. Location transparency refers to the fact that the

10 1 Introduction

command used to perform a task is independent of both the location of the data and the system on which an operation is carried out. Naming transparency means that a unique name is provided for each object in the database. In the absence of naming transparency, users are required to embed the location name (or an identifier) as part of the object name.

1.4.1.3 Replication Transparency

The issue of replicating data within a distributed database is introduced in Chapter 3 and discussed in detail in Chapter 13. At this point, let us just mention that for performance, reliability, and availability reasons, it is usually desirable to be able to distribute data in a replicated fashion across the machines on a network. Such replication helps performance since diverse and conflicting user requirements can be more easily accommodated. For example, data that are commonly accessed by one user can be placed on that user’s local machine as well as on the machine of another user with the same access requirements. This increases the locality of reference. Furthermore, if one of the machines fails, a copy of the data are still available on another machine on the network. Of course, this is a very simple-minded description of the situation. In fact, the decision as to whether to replicate or not, and how many copies of any database object to have, depends to a considerable degree on user applications. We will discuss these in later chapters.

Assuming that data are replicated, the transparency issue is whether the users should be aware of the existence of copies or whether the system should handle the management of copies and the user should act as if there is a single copy of the data (note that we are not referring to the placement of copies, only their existence). From a user’s perspective the answer is obvious. It is preferable not to be involved with handling copies and having to specify the fact that a certain action can and/or should be taken on multiple copies. From a systems point of view, however, the answer is not that simple. As we will see in Chapter 11, when the responsibility of specifying that an action needs to be executed on multiple copies is delegated to the user, it makes transaction management simpler for distributed DBMSs. On the other hand, doing so inevitably results in the loss of some flexibility. It is not the system that decides whether or not to have copies and how many copies to have, but the user application. Any change in these decisions because of various considerations definitely affects the user application and, therefore, reduces data independence considerably. Given these considerations, it is desirable that replication transparency be provided as a standard feature of DBMSs. Remember that replication transparency refers only to the existence of replicas, not to their actual location. Note also that distributing these replicas across the network in a transparent manner is the domain of network transparency.

1.4 Promises of DDBSs 11

1.4.1.4 Fragmentation Transparency

The final form of transparency that needs to be addressed within the context of a distributed database system is that of fragmentation transparency. In Chapter 3 we discuss and justify the fact that it is commonly desirable to divide each database relation into smaller fragments and treat each fragment as a separate database object (i.e., another relation). This is commonly done for reasons of performance, avail- ability, and reliability. Furthermore, fragmentation can reduce the negative effects of replication. Each replica is not the full relation but only a subset of it; thus less space is required and fewer data items need be managed.

There are two general types of fragmentation alternatives. In one case, called horizontal fragmentation, a relation is partitioned into a set of sub-relations each of which have a subset of the tuples (rows) of the original relation. The second alternative is vertical fragmentation where each sub-relation is defined on a subset of the attributes (columns) of the original relation.

When database objects are fragmented, we have to deal with the problem of handling user queries that are specified on entire relations but have to be executed on subrelations. In other words, the issue is one of finding a query processing strategy based on the fragments rather than the relations, even though the queries are specified on the latter. Typically, this requires a translation from what is called a global query to several fragment queries. Since the fundamental issue of dealing with fragmentation transparency is one of query processing, we defer the discussion of techniques by which this translation can be performed until Chapter 7.

1.4.1.5 Who Should Provide Transparency?

In previous sections we discussed various possible forms of transparency within a distributed computing environment. Obviously, to provide easy and efficient access by novice users to the services of the DBMS, one would want to have full trans- parency, involving all the various types that we discussed. Nevertheless, the level of transparency is inevitably a compromise between ease of use and the difficulty and overhead cost of providing high levels of transparency. For example, Gray argues that full transparency makes the management of distributed data very difficult and claims that “applications coded with transparent access to geographically distributed databases have: poor manageability, poor modularity, and poor message performance” [Gray, 1989]. He proposes a remote procedure call mechanism between the requestor users and the server DBMSs whereby the users would direct their queries to a specific DBMS. This is indeed the approach commonly taken by client/server systems that we discuss shortly.

What has not yet been discussed is who is responsible for providing these services. It is possible to identify three distinct layers at which the transparency services can be provided. It is quite common to treat these as mutually exclusive means of providing the service, although it is more appropriate to view them as complementary.