Semantics and implementation of continuous sliding window queries over data streams

ABSTRACT

In recent years the processing of continuous queries over potentially infinite data streams has attracted a lot of research attention. We observed that the majority of work addresses individual stream operations and system-related issues rather than the development of a general-purpose basis for stream processing systems. Furthermore, example continuous queries are often formulated in some declarative query language without specifying the underlying semantics precisely enough. To overcome these deficiencies, this article presents a consistent and powerful operator algebra for data streams which ensures that continuous queries have well-defined, deterministic results. In analogy to traditional database systems, we distinguish between a logical and a physical operator algebra. While the logical algebra specifies the semantics of the individual operators in a descriptive but concrete way over temporal multisets, the physical algebra provides efficient implementations in the form of stream-to-stream operators. By adapting and enhancing research from temporal databases to meet the challenging requirements in streaming applications, we are able to carry over the conventional transformation rules from relational databases to stream processing. For this reason, our approach not only makes it possible to express continuous queries with a sound semantics, but also provides a solid foundation for query optimization, one of the major research topics in the stream community. Since this article seamlessly explains the steps from query formulation to query execution, it outlines the innovative features and operational functionality implemented in our state-of-the-art stream processing infrastructure.

REFERENCES

• 1: Daniel J. Abadi , Don Carney , Ugur Çetintemel , Mitch Cherniack , Christian Convey , Sangdon Lee , Michael Stonebraker , Nesime Tatbul , Stan Zdonik, Aurora: a new model and architecture for data stream management, The VLDB Journal — The International Journal on Very Large Data Bases, v.12 n.2, p.120-139, August 2003 [doi>10.1007/s00778-003-0095-z]
• 2: Arvind Arasu , Brian Babcock , Shivnath Babu , Jon McAlister , Jennifer Widom, Characterizing memory requirements for queries over continuous data streams, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543642]
• 3: Arvind Arasu , Shivnath Babu , Jennifer Widom, The CQL continuous query language: semantic foundations and query execution, The VLDB Journal — The International Journal on Very Large Data Bases, v.15 n.2, p.121-142, June 2006 [doi>10.1007/s00778-004-0147-z]
• 4: Brian Babcock , Shivnath Babu , Rajeev Motwani , Mayur Datar, Chain: operator scheduling for memory minimization in data stream systems, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872789]
• 5: Brian Babcock , Shivnath Babu , Mayur Datar , Rajeev Motwani , Jennifer Widom, Models and issues in data stream systems, Proceedings of the twenty-first ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 03-05, 2002, Madison, Wisconsin [doi>10.1145/543613.543615]
• 6: Shivnath Babu , Kamesh Munagala , Jennifer Widom , Rajeev Motwani, Adaptive Caching for Continuous Queries, Proceedings of the 21st International Conference on Data Engineering, p.118-129, April 05-08, 2005 [doi>10.1109/ICDE.2005.15]
• 7: Yijian Bai , Hetal Thakkar , Haixun Wang , Chang Luo , Carlo Zaniolo, A data stream language and system designed for power and extensibility, Proceedings of the 15th ACM international conference on Information and knowledge management, November 06-11, 2006, Arlington, Virginia, USA [doi>10.1145/1183614.1183664]
• 8: Barga, R. S., Goldstein, J., Ali, M. H., and Hong, M. 2007. Consistent streaming through time: A vision for event stream processing. In Proceedings of the Conference on Innovative Data Systems Research (CIDR), 363--374.
• 9: Michael Cammert , Jurgen Kramer , Bernhard Seeger , Sonny Vaupel, A Cost-Based Approach to Adaptive Resource Management in Data Stream Systems, IEEE Transactions on Knowledge and Data Engineering, v.20 n.2, p.230-245, February 2008 [doi>10.1109/TKDE.2007.190686]
• 10: Don Carney , Uğur Çetintemel , Alex Rasin , Stan Zdonik , Mitch Cherniack , Mike Stonebraker, Operator scheduling in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.838-849, September 09-12, 2003, Berlin, Germany
• 11: Chandrasekaran, S., Cooper, O., Deshpande, A., and et al. 2003. TelegraphCQ: Continuous dataflow processing for an uncertain world. In Proceedings of the Conference on Innovative Data Systems Research (CIDR).
• 12: Sirish Chandrasekaran , Michael J. Franklin, Streaming queries over streaming data, Proceedings of the 28th international conference on Very Large Data Bases, p.203-214, August 20-23, 2002, Hong Kong, China
• 13: Surajit Chaudhuri , Rajeev Motwani , Vivek Narasayya, On random sampling over joins, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.263-274, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 14: Jianjun Chen , David J. DeWitt , Feng Tian , Yuan Wang, NiagaraCQ: a scalable continuous query system for Internet databases, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.379-390, May 15-18, 2000, Dallas, Texas, United States
• 15: Thomas H. Cormen , Clifford Stein , Ronald L. Rivest , Charles E. Leiserson, Introduction to Algorithms, McGraw-Hill Higher Education, 2001
• 16: Chuck Cranor , Theodore Johnson , Oliver Spataschek , Vladislav Shkapenyuk, Gigascope: a stream database for network applications, Proceedings of the 2003 ACM SIGMOD international conference on Management of data, June 09-12, 2003, San Diego, California [doi>10.1145/872757.872838]
• 17: Mayur Datar , Aristides Gionis , Piotr Indyk , Rajeev Motwani, Maintaining stream statistics over sliding windows: (extended abstract), Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.635-644, January 06-08, 2002, San Francisco, California
• 18: Umeshwar Dayal, Of Nests and Trees: A Unified Approach to Processing Queries That Contain Nested Subqueries, Aggregates, and Quantifiers, Proceedings of the 13th International Conference on Very Large Data Bases, p.197-208, September 01-04, 1987
• 19: Umeshwar Dayal , Nathan Goodman , Randy H. Katz, An extended relational algebra with control over duplicate elimination, Proceedings of the 1st ACM SIGACT-SIGMOD symposium on Principles of database systems, March 29-31, 1982, Los Angeles, California [doi>10.1145/588111.588132]
• 20: Demers, A. J., Gehrke, J., Panda, B., Riedewald, M., Sharma, V., and White, W. M. 2007. Cayuga: A General purpose event monitoring system. In Proceedings of the Conference on Innovative Data Systems Research (CIDR), 412--422.
• 21: Jens-Peter Dittrich , Bernhard Seeger , David Scot Taylor , Peter Widmayer, Progressive merge join: a generic and non-blocking sort-based join algorithm, Proceedings of the 28th international conference on Very Large Data Bases, p.299-310, August 20-23, 2002, Hong Kong, China
• 22: Dengfeng Gao , S. Jensen , T. Snodgrass , D. Soo, Join operations in temporal databases, The VLDB Journal — The International Journal on Very Large Data Bases, v.14 n.1, p.2-29, March 2005 [doi>10.1007/s00778-003-0111-3]
• 23: Hector Garcia-Molina , Jennifer Widom , Jeffrey D. Ullman, Database System Implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1999
• 24: Thanaa M. Ghanem , Moustafa A. Hammad , Mohamed F. Mokbel , Walid G. Aref , Ahmed K. Elmagarmid, Incremental Evaluation of Sliding-Window Queries over Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.19 n.1, p.57-72, January 2007 [doi>10.1109/TKDE.2007.12]
• 25: Lukasz Golab , M Tamer Özsu, Processing sliding window multi-joins in continuous queries over data streams, Proceedings of the 29th international conference on Very large data bases, p.500-511, September 09-12, 2003, Berlin, Germany
• 26: Lukasz Golab , M. Tamer Özsu, Issues in data stream management, ACM SIGMOD Record, v.32 n.2, p.5-14, June 2003 [doi>10.1145/776985.776986]
• 27: Lukasz Golab , M. Tamer Özsu, Update-pattern-aware modeling and processing of continuous queries, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066232]
• 28: Goetz Graefe, Query evaluation techniques for large databases, ACM Computing Surveys (CSUR), v.25 n.2, p.73-169, June 1993 [doi>10.1145/152610.152611]
• 29: Jim Gray , Surajit Chaudhuri , Adam Bosworth , Andrew Layman , Don Reichart , Murali Venkatrao , Frank Pellow , Hamid Pirahesh, Data Cube: A Relational Aggregation Operator Generalizing Group-By, Cross-Tab, and Sub-Totals, Data Mining and Knowledge Discovery, v.1 n.1, p.29-53, 1997 [doi>10.1023/A:1009726021843]
• 30: Sudipto Guha , Adam Meyerson , Nina Mishra , Rajeev Motwani , Liadan O'Callaghan, Clustering Data Streams: Theory and Practice, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.515-528, March 2003 [doi>10.1109/TKDE.2003.1198387]
• 31: Peter J. Haas , Joseph M. Hellerstein, Ripple joins for online aggregation, Proceedings of the 1999 ACM SIGMOD international conference on Management of data, p.287-298, May 31-June 03, 1999, Philadelphia, Pennsylvania, United States
• 32: Joseph M. Hellerstein , Peter J. Haas , Helen J. Wang, Online aggregation, Proceedings of the 1997 ACM SIGMOD international conference on Management of data, p.171-182, May 11-15, 1997, Tucson, Arizona, United States
• 33: Curtis Dyreson , Fabio Grandi , Wolfgang Käfer , Nick Kline , Nikos Lorentzos , Yannis Mitsopoulos , Angelo Montanari , Daniel Nonen , Elisa Peressi , Barbara Pernici , John F. Roddick , Nandlal L. Sarda , Maria Rita Scalas , Arie Segev , Richard Thomas Snodgrass , Mike D. Soo , Abdullah Tansel , Paolo Tiberio , Gio Wiederhold, A consensus glossary of temporal database concepts, ACM SIGMOD Record, v.23 n.1, p.52-64, March 1994 [doi>10.1145/181550.181560]
• 34: Kang, J., Naughton, J., and Viglas, S. 2003. Evaluating window joins over unbounded streams. In Proceedings of the International Conference on Data Engineering (ICDE), 341--352.
• 35: Richard M. Karp , Scott Shenker , Christos H. Papadimitriou, A simple algorithm for finding frequent elements in streams and bags, ACM Transactions on Database Systems (TODS), v.28 n.1, p.51-55, March 2003 [doi>10.1145/762471.762473]
• 36: Krämer, J. 2007. Continuous queries over data streams -- Semantics and implementation. Ph.D. thesis, University of Marburg.
• 37: Jürgen Krämer , Bernhard Seeger, PIPES: a public infrastructure for processing and exploring streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007699]
• 38: Krämer, J. and Seeger, B. 2005. A temporal foundation for continuous queries over data streams. In Proceedings of the International Conference on Management of Data (COMAD), 70--82.
• 39: Yan-Nei Law , Haixun Wang , Carlo Zaniolo, Query languages and data models for database sequences and data streams, Proceedings of the Thirtieth international conference on Very large data bases, p.492-503, August 31-September 03, 2004, Toronto, Canada
• 40: Jin Li , David Maier , Kristin Tufte , Vassilis Papadimos , Peter A. Tucker, Semantics and evaluation techniques for window aggregates in data streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066193]
• 41: Samuel Madden , Michael J. Franklin , Joseph M. Hellerstein , Wei Hong, TAG: a Tiny AGgregation service for Ad-Hoc sensor networks, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060303]
• 42: Gurmeet Singh Manku , Rajeev Motwani, Approximate frequency counts over data streams, Proceedings of the 28th international conference on Very Large Data Bases, p.346-357, August 20-23, 2002, Hong Kong, China
• 43: J. Nievergelt , F. P. Preparata, Plane-sweep algorithms for intersecting geometric figures, Communications of the ACM, v.25 n.10, p.739-747, Oct 1982 [doi>10.1145/358656.358681]
• 44: Patroumpas, K. and Sellis, T. K. 2006. Window specification over data streams. In Proceedings of the EDBT Workshops, 445--464.
• 45: Raman, V., Deshpande, A., and Hellerstein, J. M. 2003. Using state modules for adaptive query processing. In Proceedings of the International Conference on Data Engineering (ICDE), 353.
• 46: Prasan Roy , S. Seshadri , S. Sudarshan , Siddhesh Bhobe, Efficient and extensible algorithms for multi query optimization, Proceedings of the 2000 ACM SIGMOD international conference on Management of data, p.249-260, May 15-18, 2000, Dallas, Texas, United States
• 47: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 48: Giedrius Slivinskas , Christian S. Jensen , Richard Thomas Snodgrass, A Foundation for Conventional and Temporal Query Optimization Addressing Duplicates and Ordering, IEEE Transactions on Knowledge and Data Engineering, v.13 n.1, p.21-49, January 2001 [doi>10.1109/69.908979]
• 49: SQR. 2003. SQR -- A stream query repository. http://www.db.stanford.edu/stream/sqr.
• 50: Utkarsh Srivastava , Jennifer Widom, Flexible time management in data stream systems, Proceedings of the twenty-third ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, June 14-16, 2004, Paris, France [doi>10.1145/1055558.1055596]
• 51: Abdullah Uz Tansel , James Clifford , Shashi Gadia , Sushil Jajodia , Arie Segev , Richard Snodgrass, Temporal databases: theory, design, and implementation, Benjamin-Cummings Publishing Co., Inc., Redwood City, CA, 1993
• 52: Nesime Tatbul , Uğur Çetintemel , Stan Zdonik , Mitch Cherniack , Michael Stonebraker, Load shedding in a data stream manager, Proceedings of the 29th international conference on Very large data bases, p.309-320, September 09-12, 2003, Berlin, Germany
• 53: Peter A. Tucker , David Maier , Tim Sheard , Leonidas Fegaras, Exploiting Punctuation Semantics in Continuous Data Streams, IEEE Transactions on Knowledge and Data Engineering, v.15 n.3, p.555-568, March 2003 [doi>10.1109/TKDE.2003.1198390]
• 54: Tucker, P. A., Tufte, K., Papadimos, V., and Maier, D. 2002. NEXMark -- A benchmark for queries over data streams. http://www.cse.ogi.edu/dot/niagara/NEXMark.
• 55: Stratis D. Viglas , Jeffrey F. Naughton, Rate-based query optimization for streaming information sources, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564697]
• 56: Stratis D. Viglas , Jeffrey F. Naughton , Josef Burger, Maximizing the output rate of multi-way join queries over streaming information sources, Proceedings of the 29th international conference on Very large data bases, p.285-296, September 09-12, 2003, Berlin, Germany
• 57: Haixun Wang , Carlo Zaniolo , Chang Richard Luo, ATLAS: a small but complete SQL extension for data mining and data streams, Proceedings of the 29th international conference on Very large data bases, p.1113-1116, September 09-12, 2003, Berlin, Germany
• 58: Jun Yang , Jennifer Widom, Incremental Computation and Maintenance of Temporal Aggregates, Proceedings of the 17th International Conference on Data Engineering, p.51-60, April 02-06, 2001
• 59: Yin Yang , Jurgen Kramer , Dimitris Papadias , Bernhard Seeger, HybMig: A Hybrid Approach to Dynamic Plan Migration for Continuous Queries, IEEE Transactions on Knowledge and Data Engineering, v.19 n.3, p.398-411, March 2007 [doi>10.1109/TKDE.2007.43]
• 60: Yali Zhu , Elke A. Rundensteiner , George T. Heineman, Dynamic plan migration for continuous queries over data streams, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007617]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.4 Systems
          Subjects: Query processing

Additional Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
      H.1.0 General

General Terms:
Algorithms

Keywords:
Semantics, continuous queries, data streams, query optimization