A data stream language and system designed for power and extensibility

ABSTRACT

By providing an integrated and optimized support for user-defined aggregates (UDAs), data stream management systems (DSMS) can achieve superior power and generality while preserving compatibility with current SQL standards. This is demonstrated by the Stream Mill system that, through is Expressive Stream Language (ESL), efficiently supports a wide range of applications - including very advanced ones such as data stream mining, streaming XML processing, time-series queries, and RFID event processing. ESL supports physical and logical windows (with optional slides and tumbles) on both built-in aggregates and UDAs, using a simple framework that applies uniformly to both aggregate functions written in an external procedural languages and those natively written in ESL. The constructs introduced in ESL extend the power and generality of DSMS, and are conducive to UDA-specific optimization and efficient execution as demonstrated by several experiments.

REFERENCES

• 1: Oracle. http://www.oracle.com/technology/documentation/database10gr2.html.
• 2: A. Arasu, S. Babu, and J. Widom. CQL: A language for continuous queries over streams and relations. In DBPL, pages 1--19, 2003.
• 3: Arvind Arasu and Jennifer Widom. Resource sharing in continuous sliding-window aggregates. In VLDB, pages 336--347, 2004.
• 4: 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]
• 5: Brian Babcock , Mayur Datar , Rajeev Motwani, Sampling from a moving window over streaming data, Proceedings of the thirteenth annual ACM-SIAM symposium on Discrete algorithms, p.633-634, January 06-08, 2002, San Francisco, California
• 6: Y. Bai, C. Luo, H. Thakkar, and C. Zaniolo. Efficient support for time series queries in data stream management systems. In Stream Data Management - Chapter 6. N. Chaudhry, K. Shaw and M. Abdelguerfi (EDs.), Kluwer, 2004.
• 7: Y. Bai, H. Thakkar, H. Wang, and C. Zaniolo. Timestamp management and operator scheduling in Stream Mill DSMS. Technical report, Department of Computer Science, UCLA, June 2006.
• 8: D. Barbara. The characterization of continuous queries. Intl. Journal of Cooperative Information Systems, 8(4):295--323, 1999.
• 9: Graham Cormode , Theodore Johnson , Flip Korn , S. Muthukrishnan , Oliver Spatscheck , Divesh Srivastava, Holistic UDAFs at streaming speeds, Proceedings of the 2004 ACM SIGMOD international conference on Management of data, June 13-18, 2004, Paris, France [doi>10.1145/1007568.1007575]
• 10: Chuck Cranor , Yuan Gao , Theodore Johnson , Vlaidslav Shkapenyuk , Oliver Spatscheck, Gigascope: high performance network monitoring with an SQL interface, Proceedings of the 2002 ACM SIGMOD international conference on Management of data, June 03-06, 2002, Madison, Wisconsin [doi>10.1145/564691.564777]
• 11: 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]
• 12: 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
• 13: Cheqing Jin , Weining Qian , Chaofeng Sha , Jeffrey X. Yu , Aoying Zhou, Dynamically maintaining frequent items over a data stream, Proceedings of the twelfth international conference on Information and knowledge management, November 03-08, 2003, New Orleans, LA, USA [doi>10.1145/956863.956918]
• 14: 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]
• 15: D. Abadi et al. The design of the borealis stream processing engine. CIDR, 12(2):120--139, 2005.
• 16: D. Carney et al. Monitoring streams - a new class of data management applications. In VLDB, Hong Kong, China, 2002.
• 17: 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]
• 18: 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]
• 19: Sirish Chandrasekaran et al. Telegraphcq: Continuous dataflow processing for an uncertain world. In CIDR, 2003.
• 20: Theodore Johnson , S. Muthukrishnan , Irina Rozenbaum, Sampling algorithms in a stream operator, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066159]
• 21: 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]
• 22: 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]
• 23: M. Hammad, W. Aref, M. Franklin, M. Mokbel, and A.K. Elmagarmid. Efficient execution of sliding window queries over data streams. Technical report, Department of Computer Sciences, Purdue University, December 2003.
• 24: Yan-Nei Law, Haixun Wang, and Carlo Zaniolo. Data models and query language for data streams. In VLDB, pages 492--503, 2004.
• 25: Chang Luo , Hetal Thakkar , Haixun Wang , Carlo Zaniolo, A native extension of SQL for mining data streams, Proceedings of the 2005 ACM SIGMOD international conference on Management of data, June 14-16, 2005, Baltimore, Maryland [doi>10.1145/1066157.1066271]
• 26: Reza Sadri , Carlo Zaniolo , Amir Zarkesh , Jafar Adibi, Optimization of sequence queries in database systems, Proceedings of the twentieth ACM SIGMOD-SIGACT-SIGART symposium on Principles of database systems, p.71-81, May 2001, Santa Barbara, California, United States [doi>10.1145/375551.375563]
• 27: Praveen Seshadri , Miron Livny , Raghu Ramakrishnan, The Design and Implementation of a Sequence Database System, Proceedings of the 22th International Conference on Very Large Data Bases, p.99-110, September 03-06, 1996
• 28: Sleepycat Software, http://www.sleepycat.com. The Berkeley Database (Berkeley DB).
• 29: Fusheng Wang, Shaorong Liu, Peiya Liu, and Yijian Bai. Bridging physical and virtual worlds: Complex event processing for RFID data streams. In EDBT, 2006.
• 30: Haixun Wang and Carlo Zaniolo. ATLaS: a native extension of SQL for data minining. In Proceedings of Third SIAM Int. Conference on Data Mining, pages 130--141, 2003.
• 31: Fred Zemke, Krishna Kulkarni, Andy Witkowski, and Bob Lyle. Proposal for OLAP functions. In ISO/IEC JTC1/SC32 WG3:YGJ-nnn, ANSI NCITS H2-99-155, 1999.
• 32: Donghui Zhang , Dimitrios Gunopulos , Vassilis J. Tsotras , Bernhard Seeger, Temporal Aggregation over Data Streams Using Multiple Granularities, Proceedings of the 8th International Conference on Extending Database Technology: Advances in Database Technology, p.646-663, March 25-27, 2002
• 33: Xin Zhou , Hetal Thakkar , Carlo Zaniolo, Unifying the Processing of XML Streams and Relational Data Streams, Proceedings of the 22nd International Conference on Data Engineering (ICDE'06), p.50, April 03-07, 2006 [doi>10.1109/ICDE.2006.165]

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages

General Terms:
Languages

Keywords:
data stream, data stream management system, query language