Stream Data Management

by CHAUDHRY, NAUMAN A.; Shaw, Kevin; Abdelguerfi, Mahdi

• ISBN13: 9780387243931
• ISBN10: 0387243933
• Format: Hardcover
• Copyright: 2005-03-30
• Publisher: Springer-Verlag New York Inc

Summary

Researchers in data management have recently recognized the importance of a new class of data-intensive applications that requires managing data streams, i.e., data composed of continuous, real-time sequence of items. Streaming applications pose new and interesting challenges for data management systems. Such application domains require queries to be evaluated continuously as opposed to the one time evaluation of a query for traditional applications. Streaming data sets grow continuously and queries must be evaluated on such unbounded data sets. These, as well as other challenges, require a major rethink of almost all aspects of traditional database management systems to support streaming applications. Stream Data Management comprises eight invited chapters by researchers active in stream data management. The collected chapters provide exposition of algorithms, languages, as well as systems proposed and implemented for managing streaming data. Stream Data Management is designed to appeal to researchers or practitioners already involved in stream data management, as well as to those starting out in this area. This book is also suitable for graduate students in computer science interested in learning about stream data management.

Table of Contents

List of Figures	ix
List of Tables	xi
Preface	xiii
1 Introduction to Stream Data Management	1	(14)
Nauman A. Chaudhry
1. Why Stream Data Management?	1	(5)
1.1 Streaming Applications	2	(1)
1.2 Traditional Database Management Systems and Streaming Applications	3	(1)
1.3 Towards Stream Data Management Systems	4	(1)
1.4 Outline of the Rest of the Chapter	5	(1)
2. Stream Data Models and Query Languages	6	(2)
2.1 Timestamps	6	(1)
2.2 Windows	6	(1)
2.3 Proposed Stream Query Languages	7	(1)
3. Implementing Stream Query Operators	8	(1)
3.1 Query Operators and Optimization	8	(1)
3.2 Performance Measurement	8	(1)
4. Prototype Stream Data Management Systems	9	(1)
5. Tour of the Book	10	(1)
Acknowledgements	11	(1)
References	11	(4)
2 Query Execution and Optimization	15	(20)
Stratis D. Viglas
1. Introduction	15	(1)
2. Query Execution	16	(6)
2.1 Projections and Selections	17	(1)
2.2 Join Evaluation	18	(4)
3. Static Optimization	22	(6)
3.1 Rate-based Query Optimization	23	(1)
3.2 Resource Allocation and Operator Scheduling	24	(2)
3.3 Quality of Service and Load Shedding	26	(2)
4. Adaptive Evaluation	28	(3)
4.1 Query Scrambling	28	(1)
4.2 Eddies and Stems	29	(2)
5. Summary	31	(1)
References	32	(3)
3 Filtering, Punctuation, Windows and Synopses	35	(24)
David Maier; Peter A. Tucker, and Minos Garofalakis
1. Introduction: Challenges for Processing Data Streams	36	(1)
2. Stream Filtering: Volume Reduction	37	(3)
2.1 Precise Filtering	37	(1)
2.2 Data Merging	38	(1)
2.3 Data Dropping	38	(2)
2.4 Filtering with Multiple Queries	40	(1)
3. Punctuations: Handling Unbounded Behavior by Exploiting Stream Semantics	40	(6)
3.1 Punctuated Data Streams	41	(1)
3.2 Exploiting Punctuations	41	(2)
3.3 Using Punctuations in the Example Query	43	(1)
3.4 Sources of Punctuations	44	(1)
3.5 Open Issues	45	(1)
3.6 Summary	46	(1)
4. Windows: Handling Unbounded Behavior by Modifying Queries	46	(1)
5. Dealing with Disorder	47	(3)
5.1 Sources of Disorder	47	(1)
5.2 Handling Disorder	48	(2)
5.3 Summary	50	(1)
6. Synopses: Processing with Bounded Memory	50	(5)
6.1 Data-Stream Processing Model	51	(1)
6.2 Sketching Streams by Random Linear Projections: AMS Sketches	51	(3)
6.3 Sketching Streams by Hashing: FM Sketches	54	(1)
6.4 Summary	55	(1)
7. Discussion	55	(1)
Acknowledgments	56	(1)
References	56	(3)
4 XML & Data Streams	59	(24)
Nicolas Bruno, Luis Gravano, Nick Koudas, and Divesh Srivastava
1. Introduction	60	(3)
1.1 XML Databases	60	(1)
1.2 Streaming XML	61	(1)
1.3 Contributions	62	(1)
2. Models and Problem Statement	63	(3)
2.1 XML Documents	63	(1)
2.2 Query Language	64	(1)
2.3 Streaming Model	65	(1)
2.4 Problem Statement	65	(1)
3. XML Multiple Query Processing	66	(10)
3.1 Prefix Sharing	66	(1)
3.2 Y-Filter: A Navigation-Based Approach	67	(2)
3.3 Index-Filter: An Index-Based Approach	69	(6)
3.4 Summary of Experimental Results	75	(1)
4. Related Work	76	(2)
4.1 XML Databases	76	(1)
4.2 Streaming XML	77	(1)
4.3 Relational Stream Query Processing	78	(1)
5. Conclusions	78	(1)
References	79	(4)
5 CAPE: A Constraint-Aware Adaptive Stream Processing Engine	83	(30)
Elke A. Rundenrteiner, Luping Ding, Yali Zhu, Timothy Sutherland and Bradffbrd Pielech
1. Introduction	83	(2)
1.1 Challenges in Streaming Data Processing	83	(1)
1.2 State-of-the-Art Stream Processing Systems	84	(1)
1.3 CAPE: Adaptivity and Constraint Exploitation	85	(1)
2. CAPE System Overview	85	(2)
3. Constraint-Exploiting Reactive Query Operators	87	(6)
3.1 Issues with Stream Join Algorithm	88	(1)
3.2 Constraint-Exploiting Join Algorithm	88	(2)
3.3 Optimizations Enabled by Combined Constraints	90	(1)
3.4 Adaptive Component-Based Execution Logic	91	(2)
3.5 Summary of Performance Evaluation	93	(1)
4. Adaptive Execution Scheduling	93	(5)
4.1 State-of-the-Art Operator Scheduling	94	(1)
4.2 The ASSA Framework	94	(1)
4.3 The ASSA Strategy: Metrics, Scoring and Selection	95	(3)
4.4 Summary of Performance Evaluation	98	(1)
5. Run-time Plan Optimization and Migration	98	(6)
5.1 Timing of Plan Re-optimization	99	(1)
5.2 Optimization Opportunities and Heuristics	99	(2)
5.3 New Issues for Dynamic Plan Migration	101	(1)
5.4 Migration Strategies in CAPE	102	(2)
6. Self-Adjusting Plan Distribution across Machines	104	(5)
6.1 Distributed Stream Processing Architecture	104	(2)
6.2 Strategies for Query Operator Distribution	106	(1)
6.3 Static Distribution Evaluation	107	(1)
6.4 Self-Adaptive Redistribution Strategies	107	(1)
6.5 Run-Time Redistribution Evaluation	108	(1)
7. Conclusion	109	(1)
References	109	(4)
6 Time Series Queries in Data Stream Management Systems	113	(20)
Yijian Rai, Chang R. Luo, Hetal Thakkar and Carlo Zaniolo
1. Introduction	113	(3)
2. The ESL-TS Language	116	(5)
2.1 Repeating Patterns and Aggregates	117	(3)
2.2 Comparison with other Languages	120	(1)
3. ESL and User Defined Aggregates	121	(4)
4. ESL-TS Implementation	125	(2)
5. Optimization	127	(2)
6. Conclusion	129	(1)
Acknowledgments	130	(1)
References	130	(3)
7 Managing Distributed Geographical Data Streams with the GIDB Protal System	133	(20)
John T. Sample, Frank P. McCreedy, and Michael Thomas
1. Introduction	133	(1)
2. Geographic Data Servers	134	(5)
2.1 Types of Geographic Data	134	(2)
2.2 Types of Geographic Data Servers	136	(1)
2.3 Transport Mechanisms	137	(1)
2.4 Geographic Data Standards	138	(1)
2.5 Geographic Data Streams	139	(1)
3. The Geospatial Information Database Portal System	139	(8)
3.1 GIDB Data Sources	139	(1)
3.2 GIDB Internals	140	(2)
3.3 GIDB Access Methods	142	(2)
3.4 GIDB Thematic Layer Server	144	(3)
4. Example Scenarios	147	(3)
4.1 Serving Moving Objects	147	(2)
4.2 Serving Meteorological and Oceanographic Data	149	(1)
Acknowledgements	150	(1)
References	150	(3)
8 Streaming Data Dissemination using Peer-Peer Systems	153	(16)
Shetal Shah, and Krithi Ramamritham
1. Introduction	153	(1)
2. Information-based Peer-Peer systems	154	(6)
2.1 Summary of Issues in Information-Based Peer-Peer Systems	154	(2)
2.2 Some Existing Peer-Peer Systems	156	(1)
2.3 Napster	157	(1)
2.4 Gnutella	157	(1)
2.5 Gia	157	(1)
2.6 Semantic Overlay Networks	158	(1)
2.7 Distributed Hash Tables	158	(2)
3. Multimedia Streaming Using Peer-Peer Systems	160	(1)
4. Peer-Peer Systems for Dynamic Data Dissemination	161	(5)
4.1 Overview of Data Dissemination Techniques	162	(1)
4.2 Coherence Requirement	163	(1)
4.3 A Peer-Peer Repository Framework	164	(2)
5. Conclusions	166	(1)
References	167	(2)
Index	169