International Handbooks on Information Systems Series Editors Peter Bernus . Jacek Blazewicz . Gunter Schmidt· Michael Shaw Springer Berlin Heidelberg New York Hong Kong London Milan Paris Tokyo Titles in the Series P. Bemus, K. Mertins and G. Schmidt (Eds.) Handbook on Architectures of Information Systems ISBN 3-540-64453-9 M. Shaw, R. Blanning, T. Strader and A. Whinston (Eds.) Handbook on Electronic Commerce ISBN 3-540-65822-X J. Blazewicz, K. Ecker, B. Plateau and D. Trystram (Eds.) Handbook on Parallel and Distributed Processing ISBN 3-540-66441-6 H. H.Adelsberger, B. Collis and J. M. Pawlowski (Eds.) Handbook on Information Technologies for Education and Training ISBN 3-540-67803-4 C. W. Holsapple (Ed.) Handbook on Knowledge Management 1 Knowledge Matters ISBN 3-540-43527-1 Handbook on Knowledge Management 2 Knowledge Directions ISBN 3-540-43527-1 P. Bemus, L. Nemes and G. Schmidt (Eds.) Handbook on Enterprise Architecture ISBN 3-540-00343-6 J. Blazewicz, W. Kubiak, T. Morzy and M. Rusinkiewicz (Eds.) Handbook on Data Management in Information Systems ISBN 3-540-43893-9 Ja cek Blaiewicz . Wieslaw Kubiak Tadeusz Morzy . Marek Rusinkiewicz Editors Handbook on Data Management in Information Systems With 157 Figures and 9 Tables Springer Professor Jacek Blazewicz e-mail: [email protected] Institute of Bioorganic Chemistry Polish Academy of Sciences ul. Noskowskiego 12 61-704 Poznan, Poland Professor Wieslaw Kubiak e-mail: [email protected] Memorial University of Newfoundland Faculty of Business Administration St. John's NF AlB 3X5, Canada Professor Tadeusz Morzy e-mail: [email protected] Poznan University of Technology Institute of Computing Science ul. Piotrowo 3a 60-965 Poznan, Poland Professor Marek Rusinkiewicz e-mail: [email protected] Telcordia Technologies Information and Computer Science Laboratory 445 South Street MCC-1J346B Morristown, NJ 07960, USA ISBN 978-3-642-53441-6 ISBN 978-3-540-24742-5 (eBook) DOI 10.1007/978-3-540-24742-5 Cataloging-in-Publication Data applied for A catalog record for this book is available from the Library of Congress. Bibliographic information published by Die Deutsche Bibliothek Die Deutsche Bibliothek lists this publication in the Deutsche Nationalbibliografie; detailed bibliographic data available in the internet at http.lldnb.ddb.de This work is subject to copyright. All rights are reserved, whether the whole or part of the material is concerned, specifically the rights of translation, reprinting, reuse of illustrations, recitation, broadcasting, reproduction on microfilm or in any other way, and storage in data banks. Duplication of this publication or parts thereof is permitted only under the provisions of the German Copyright Law of September 9, 1965, in its current version, and permission for use must always be obtained from Springer-Verlag. Violations are liable for prosecution under the German Copyright Law. Springer-Verlag Berlin Heidelberg New York a member of BertelsmannSpringer Science + Business Media GmbH http://www.springer.de © Springer-Verlag Berlin Heidelberg 2003 Softcover reprint of the hardcover 1st edition 2003 The use of general descriptive names, registered names, trademarks, etc. in this publication does not imply, even in the absence of a specific statement, that such names are exempt from the relevant protective laws and regulations and therefore free for general use. Cover design: Erich Kirchner, Heidelberg SPIN 10886050 4213130 - 5 4 3 2 1 0 - Printed on acid-free paper Foreword This book is the sixth of a running series of volumes dedicated to selected topics of information theory and practice. The objective of the series is to pro vide a reference source for problem solvers in business, industry, government, and professional researchers and gradute students. The first volume, Handbook on Architecture of Information Systems, presents a balanced number of contributions from academia and practition ers. The structure of the material follows a differentiation between model ing languages, tools and methodologies. The second volume, Handbook on Electronic Commerce, examines electronic commerce storefront, on-line busi ness, consumer interface, business-to-business networking, digital payment, legal issues, information product development and electronic business mod els. The third volume, Handbook on Parallel and Distributed Processing, presents basic concepts, methods, and recent developments in the field of parallel and distributed processing as well as some important aplications of parallel and distributed computing. In particular, the book examines such fundamental issues in the above area as languages for parallel processing, parallel operating systems, architecture of parallel and distributed systems, parallel database and multimedia systems, networking aspects of parallel and distributed systems, efficiency of parallel algorithms. The fourth volume on Information Technologies for Education and Training is· devoted to a pre sentation of current and future research and applications in the field of ed ucational technology. The fifth double volume on Knowledge Management contains an extensive, fundamental coverage of the knowledge management field. The present volume of the International Handbooks on Data Manage ment, as the previous ones, is a joint venture of an international board of editors, gathering prominent authors of academia and practice, who are well known specialists in the field of data management. The technology for data management has evolved during last 30 years from simple file systems through hierarchical, network, and relational database systems to the new generation data management technology. This transition was driven by two factors: the increasing requirements of new data management applications on one side, and recent developments in database, networking and computer technolo gies on the other side. Advances in data management technology have led to new exciting applications such as multimedia systems, digital libraries, e commerce, workflow management systems, decision support systems, etc. The intention of the Handbook is to provide practitioners, scientists and gradu ate students with a comprehensive overview of basic methods, concepts, tools and techniques applied currently for data management and their use in in formation system management and development. The handbook contains 11 chapters that cover a wide spectrum of topics ranging from core database technologies such as data modeling, relational, object-oriented, parallel and distributed database systems to advanced database systems and XML pro- VI Foreword cessing, multimedia database systems, workflow management, data warehous ing, mobile computing, and data mining. Each chapter includes a compre hensive overview of the issue covered, proposed solutions to problems, and directions for further research and development. We hope the handbook will help readers to better understand the current status of the data management field and directions of its development. Summing up, the Handbook is indispensable for academics and profes sionals who are interested in learning leading experts' coherent and individual view of the topic. We would like to express our sincere thanks to the people who have con tributed to prepare the volume. First, we would like to thank authors for their submissions. We also want to thank Dr. Muller from the Springer-Verlag for his encouragement to prepare the volume. Special thanks are addressed to Mr. Piotr Krzyzag6rski for his excellent job in careful editing and converting the chapters into a single uniform style of Springer-Verlag format. J acek Blazewicz Wieslaw Kubiak Tadeusz Morzy Marek Rusinkiewicz Contents Foreword ................ ". .................................... V 1. Management of Data: State-of-the-Art and Emerging Trends 1 Jacek Blaiewicz, Tadeusz Morzy 1 Introduction................................................. 2 2 Survey of the Volume. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 12 2. Database Systems: from File Systems to Modern Database Systems ...................................................... 18 Zbyszko K r6likowski, Tadeusz M orzy 1 Introduction - Database Concepts ............................. 19 2 Database System Generations. . . . . . . . . . . . . . . . .. . . . . . . . . . . . . ... 21 3 Network Database Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 22 4 Hierarchical Database Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 25 5 Relational Database Systems . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 29 6 Object-Oriented Database Systems. . . . . . . . . . . . . . . . . . . . . . . . . . . .. 33 7 Federated, Mediated Database Systems and Data Warehouses .. . .. 38 8 Conclusions................................................. 47 3. Data Modeling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 49 Jeffrey Parsons 1 Introduction................................................. 50 2 Early Concerns in Data Management . . . . . . . . . . . . . . . . . . . . . . . . . .. 50 3 Abstraction in Data Modeling . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 52 4 Semantic Data Models. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 56 5 Models of Reality and Perception .... . . . . . . . . . . . . . . . . . . . . . . . . .. 62 6 Toward Cognition-Based Data Management. ... .. . ... .. .. .... ... 66 7 A Cognitive Approach to Data Modeling. . . . . . . . . . . . . . . . . . . . . . .. 70 8 Research Directions .... . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 72 4. Object-Oriented Database Systems. . . . . . . . . . . . . . . . . . . . . . . .. 78 Alfons Kemper, Guido Moerkotte 1 Introduction and Motivation .................................. 80 2 Object-Oriented Data Modeling. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .. 85 3 The Query Language OQL .................................... 106 4 Physical Object Management .................................. 117 5 Architecture of Client-Server-Systems ........................... 135 6 Indexing .................................................... 139 7 Dealing with Set-Valued Attributes ............................ " 160 8 Query Optimization .......................................... 164 9 Conclusion .................................................. 186 VIII Contents 5. High Performance Parallel Database Management Systems 194 Shahram Ghandeharizadeh, Shan Gao, Chris Gahagan, Russ Krauss 1 Introduction ................................................. 195 2 Partitioning Strategies ........................................ 196 3 Join Using Inter-Operator Parallelism .......................... 201 4 ORE: a Framework for Data Migration ......................... 203 5 Conclusions and Future Research Directions ..................... 216 6. Advanced Database Systems ............................... 221 Gottfried Vossen 1 Introduction................................................. 222 2 Preliminaries................................................ 227 3 Data Models and Modeling for Complex Objects ................. 234 4 Advanced Query Languages . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 249 5 Advanced Database Server Capabilities ......................... 262 6 Conclusions and Outlook ..................................... 274 7. Parallel and Distributed Multimedia Database Systems .... 284 Odej Kao 1 Introduction................................................. 286 2 Media Fundamentals . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 288 3 MPEG as an Example of Media Compression. . . . . . . . . . . . . . . . . . . . 292 4 Organisation and Retrieval of Multimedia Data . . . . . . . . . . . . . . . . . . 298 5 Data Models for Multimedia Data. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 304 6 Multimedia Retrieval Sequence Using Images as an Example ...... 308 7 Requirements for Multimedia Applications ...................... 318 8 Parallel and Distributed Processing of Multimedia Data .......... 321 9 Parallel and Distributed Techniques for Multimedia Databases ..... 337 10 Case Study: CAIRO - Cluster Architecture for Image Retrieval and Organisation .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 348 11 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 359 8. Workflow Technology: the Support for Collaboration ....... 365 Dimitrios Georgakopoulos, Andrzej Cichocki, Marek Rusinkiewicz 1 Introduction................................................. 367 2 Application Scenario and Collaboration Requirements ............ 368 3 Commercial Technologies Addressing Collaboration Requirements . . 371 4 Evaluation of Current Workflow Management Technology . . . . . . . . . 372 5 Research Problems, Related Work, and Directions ................ 381 6 Summary................................................... 383 9. Data Warehouses .......................................... 387 Ulrich Dorndorf, Erwin Pesch 1 Introduction................................................. 389 2 Basics...................................................... 389 3 The Database of a Data Warehouse ............................ 394 Contents IX 4 The Data Warehouse Concept . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 404 5 Data Analysis of a Data Warehouse ............................ 411 6 Building a Data Warehouse ................................... 418 7 Future Research Directions. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 422 8 Conclusions................................................. 423 10. Mobile Computing ........................................ 431 Omran Bukhres, Evaggelia Pitoura, Arkady Zaslavsky 1 Introduction ................................................. 433 2 Mobile Computing Infrastructure .............................. 437 3 Mobile Computing Software Architectures and Models ................................................. 444 4 Disconnected Operation ...................................... 454 5 Weak Connectivity ........................................... 462 6 Data Delivery by Broadcast ................................... 468 7 Mobile Computing Resources and Pointers . . . . . . . . . . . . . . . . . . . . . . 476 8 Conclusions ................................................. 479 11. Data Mining .............................................. 487 Tadeusz Morzy, Maciej Zakrzewicz 1 Introduction ................................................. 488 2 Mining Associations .......................................... 490 3 Classification and Prediction .................................. 517 4 Clustering .................................................. 540 5 Conclusions ................................................. 558 Index ......................................................... 567 List of Contributors .......................................... 577 1. Management of Data: State-of-the-Art and Emerging Trends Jacek Blazewicz1 and Tadeusz Morzy2 1 Institute of Bioorganic Chemistry, Polish Academy of Sciences, Laboratory of Bioinformatics, Poznan, Poland 2 Institute of Computing Science, Poznan University of Technology, Poznan, Poland 1. Introduction ....................................................... 2 1.1 Database Systems..... .... .... ... ............ ....... ........... 3 1.2 Beyond Database Systems ...................................... 8 1.3 The Future Research .......................................... 11 2. Survey of the Volume ............................................. 12 Abstract. This chapter presents an introduction to the area of data management. The aim of the chapter is to recall the evolution of the data management during the past decades in order to present the future trends and emerging fields of research. In the second part of the chapter the brief survey of the Volume is presented. J. Błażewicz et al. (eds.), Handbook on Data Management in Information Systems © Springer-Verlag Berlin Heidelberg 2003