{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,10,5]],"date-time":"2025-10-05T16:55:22Z","timestamp":1759683322052,"version":"3.41.0"},"reference-count":59,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2009,4,1]],"date-time":"2009-04-01T00:00:00Z","timestamp":1238544000000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100001659","name":"Deutsche Forschungsgemeinschaft","doi-asserted-by":"publisher","award":["SE 553\/4-3"],"award-info":[{"award-number":["SE 553\/4-3"]}],"id":[{"id":"10.13039\/501100001659","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2009,4]]},"abstract":"<jats:p>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.<\/jats:p>","DOI":"10.1145\/1508857.1508861","type":"journal-article","created":{"date-parts":[[2009,4,21]],"date-time":"2009-04-21T14:14:44Z","timestamp":1240323284000},"page":"1-49","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":82,"title":["Semantics and implementation of continuous sliding window queries over data streams"],"prefix":"10.1145","volume":"34","author":[{"given":"J\u00fcrgen","family":"Kr\u00e4mer","sequence":"first","affiliation":[{"name":"University of Marburg, Germany"}]},{"given":"Bernhard","family":"Seeger","sequence":"additional","affiliation":[{"name":"University of Marburg, Germany"}]}],"member":"320","published-online":{"date-parts":[[2009,4,23]]},"reference":[{"key":"e_1_2_2_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0095-z"},{"key":"e_1_2_2_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543642"},{"key":"e_1_2_2_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-004-0147-z"},{"key":"e_1_2_2_4_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872789"},{"key":"e_1_2_2_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543615"},{"key":"e_1_2_2_6_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2005.15"},{"key":"e_1_2_2_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1183614.1183664"},{"volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR), 363--374","author":"Barga R. S.","key":"e_1_2_2_8_1","unstructured":"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 . 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."},{"key":"e_1_2_2_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190686"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 838--849","author":"Carney D.","key":"e_1_2_2_10_1","unstructured":"Carney , D. , Cetintemel , U. , Zdonik , S. , Rasin , A. , Cerniak , M. , and Stonebraker , M . 2003. Operator scheduling in a data stream manager . In Proceedings of the International Conference on Very Large Databases (VLDB), 838--849 . Carney, D., Cetintemel, U., Zdonik, S., Rasin, A., Cerniak, M., and Stonebraker, M. 2003. Operator scheduling in a data stream manager. In Proceedings of the International Conference on Very Large Databases (VLDB), 838--849."},{"volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR).","author":"Chandrasekaran S.","key":"e_1_2_2_11_1","unstructured":"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). 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)."},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 203--214","author":"Chandrasekaran S.","key":"e_1_2_2_12_1","unstructured":"Chandrasekaran , S. and Franklin , M. J . 2002. Streaming queries over streaming data . In Proceedings of the International Conference on Very Large Databases (VLDB), 203--214 . Chandrasekaran, S. and Franklin, M. J. 2002. Streaming queries over streaming data. In Proceedings of the International Conference on Very Large Databases (VLDB), 203--214."},{"key":"e_1_2_2_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304206"},{"key":"e_1_2_2_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335432"},{"key":"e_1_2_2_15_1","unstructured":"Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd ed. The MIT Press.   Cormen T. H. Leiserson C. E. Rivest R. L. and Stein C. 2001. Introduction to Algorithms 2nd ed. The MIT Press."},{"key":"e_1_2_2_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872838"},{"volume-title":"Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 635--644","author":"Datar M.","key":"e_1_2_2_17_1","unstructured":"Datar , M. , Gionis , A. , Indyk , P. , and Motwani , R . 2002. Maintaining stream statistics over sliding windows . In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 635--644 . Datar, M., Gionis, A., Indyk, P., and Motwani, R. 2002. Maintaining stream statistics over sliding windows. In Proceedings of the Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), 635--644."},{"key":"e_1_2_2_18_1","volume-title":"Proceedings of the International Conference on Very Large Databases, 197--208","author":"Dayal U.","year":"1987","unstructured":"Dayal , U. 1987 . Of nests and trees: A unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers . In Proceedings of the International Conference on Very Large Databases, 197--208 . Dayal, U. 1987. Of nests and trees: A unified approach to processing queries that contain nested subqueries, aggregates, and quantifiers. In Proceedings of the International Conference on Very Large Databases, 197--208."},{"key":"e_1_2_2_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/588111.588132"},{"volume-title":"Proceedings of the Conference on Innovative Data Systems Research (CIDR), 412--422","author":"Demers A. J.","key":"e_1_2_2_20_1","unstructured":"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 . 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."},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 299--310","author":"Dittrich J.-P.","key":"e_1_2_2_21_1","unstructured":"Dittrich , J.-P. , Seeger , B. , Taylor , D. S. , and Widmayer , P . 2002. Progressive merge join: A generic and non-blocking sort-based join algorithm . In Proceedings of the International Conference on Very Large Databases (VLDB), 299--310 . Dittrich, J.-P., Seeger, B., Taylor, D. S., and Widmayer, P. 2002. Progressive merge join: A generic and non-blocking sort-based join algorithm. In Proceedings of the International Conference on Very Large Databases (VLDB), 299--310."},{"key":"e_1_2_2_22_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0111-3"},{"key":"e_1_2_2_23_1","unstructured":"Garcia-Molina H. Ullman J. D. and Widom J. 2000. Database System Implementation. Prentice Hall.   Garcia-Molina H. Ullman J. D. and Widom J. 2000. Database System Implementation. Prentice Hall."},{"key":"e_1_2_2_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.12"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 500--511","author":"Golab L.","key":"e_1_2_2_25_1","unstructured":"Golab , L. and Ozsu , M . 2003a. Processing sliding window multi-joins in continuous queries over data streams . In Proceedings of the International Conference on Very Large Databases (VLDB), 500--511 . Golab, L. and Ozsu, M. 2003a. Processing sliding window multi-joins in continuous queries over data streams. In Proceedings of the International Conference on Very Large Databases (VLDB), 500--511."},{"key":"e_1_2_2_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/776985.776986"},{"key":"e_1_2_2_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066232"},{"key":"e_1_2_2_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/152610.152611"},{"key":"e_1_2_2_29_1","doi-asserted-by":"publisher","DOI":"10.1023\/A:1009726021843"},{"key":"e_1_2_2_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198387"},{"key":"e_1_2_2_31_1","doi-asserted-by":"publisher","DOI":"10.1145\/304182.304208"},{"key":"e_1_2_2_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/253260.253291"},{"key":"e_1_2_2_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/181550.181560"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE), 341--352","author":"Kang J.","key":"e_1_2_2_34_1","unstructured":"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 . 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."},{"key":"e_1_2_2_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/762471.762473"},{"key":"e_1_2_2_37_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007699"},{"volume-title":"Proceedings of the International Conference on Management of Data (COMAD), 70--82","author":"Kr\u00e4mer J.","key":"e_1_2_2_38_1","unstructured":"Kr\u00e4mer , 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 . Kr\u00e4mer, 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."},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 492--503","author":"Law Y.-N.","key":"e_1_2_2_39_1","unstructured":"Law , Y.-N. , Wang , H. , and Zaniolo , C . 2004. Query languages and data models for database sequences and data streams . In Proceedings of the International Conference on Very Large Databases (VLDB), 492--503 . Law, Y.-N., Wang, H., and Zaniolo, C. 2004. Query languages and data models for database sequences and data streams. In Proceedings of the International Conference on Very Large Databases (VLDB), 492--503."},{"key":"e_1_2_2_40_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066193"},{"key":"e_1_2_2_41_1","doi-asserted-by":"publisher","DOI":"10.5555\/1060289.1060303"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB).","author":"Manku G. S.","key":"e_1_2_2_42_1","unstructured":"Manku , G. S. and Motwani , R . 2002. Approximate frequency counts over data streams . In Proceedings of the International Conference on Very Large Databases (VLDB). Manku, G. S. and Motwani, R. 2002. Approximate frequency counts over data streams. In Proceedings of the International Conference on Very Large Databases (VLDB)."},{"key":"e_1_2_2_43_1","doi-asserted-by":"publisher","DOI":"10.1145\/358656.358681"},{"key":"e_1_2_2_44_1","doi-asserted-by":"publisher","DOI":"10.1007\/11896548_35"},{"volume-title":"Proceedings of the International Conference on Data Engineering (ICDE), 353","author":"Raman V.","key":"e_1_2_2_45_1","unstructured":"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 . 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."},{"key":"e_1_2_2_46_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335419"},{"key":"e_1_2_2_47_1","doi-asserted-by":"publisher","DOI":"10.1145\/42201.42203"},{"key":"e_1_2_2_48_1","doi-asserted-by":"publisher","DOI":"10.1109\/69.908979"},{"key":"e_1_2_2_49_1","unstructured":"SQR. 2003. SQR -- A stream query repository. http:\/\/www.db.stanford.edu\/stream\/sqr.  SQR. 2003. SQR -- A stream query repository. http:\/\/www.db.stanford.edu\/stream\/sqr."},{"key":"e_1_2_2_50_1","doi-asserted-by":"publisher","DOI":"10.1145\/1055558.1055596"},{"key":"e_1_2_2_51_1","volume-title":"Temporal Databases: Theory, Design, and Implementation. Benjamin\/Cummings.","author":"Tansel A.","year":"1993","unstructured":"Tansel , A. , Clifford , J. , Gadia , S. , Jajodia , S. , Segev , A. , and Snodgrass , R. T . 1993 . Temporal Databases: Theory, Design, and Implementation. Benjamin\/Cummings. Tansel, A., Clifford, J., Gadia, S., Jajodia, S., Segev, A., and Snodgrass, R. T. 1993. Temporal Databases: Theory, Design, and Implementation. Benjamin\/Cummings."},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 309--320","author":"Tatbul N.","key":"e_1_2_2_52_1","unstructured":"Tatbul , N. , Cetintemel , U. , Zdonik , S. B. , Cherniack , M. , and Stonebraker , M . 2003. Load shedding in a data stream manager . In Proceedings of the International Conference on Very Large Databases (VLDB), 309--320 . Tatbul, N., Cetintemel, U., Zdonik, S. B., Cherniack, M., and Stonebraker, M. 2003. Load shedding in a data stream manager. In Proceedings of the International Conference on Very Large Databases (VLDB), 309--320."},{"key":"e_1_2_2_53_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2003.1198390"},{"key":"e_1_2_2_54_1","unstructured":"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.  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."},{"key":"e_1_2_2_55_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564697"},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 285--296","author":"Viglas S. D.","key":"e_1_2_2_56_1","unstructured":"Viglas , S. D. , Naughton , J. F. , and Burger , J . 2003. Maximizing the output rate of multi-join queries over streaming information sources . In Proceedings of the International Conference on Very Large Databases (VLDB), 285--296 . Viglas, S. D., Naughton, J. F., and Burger, J. 2003. Maximizing the output rate of multi-join queries over streaming information sources. In Proceedings of the International Conference on Very Large Databases (VLDB), 285--296."},{"volume-title":"Proceedings of the International Conference on Very Large Databases (VLDB), 1113--1116","author":"Wang H.","key":"e_1_2_2_57_1","unstructured":"Wang , H. , Zaniolo , C. , and Luo , C . 2003. ATLaS: A small but complete SQL extension for data mining and data streams . In Proceedings of the International Conference on Very Large Databases (VLDB), 1113--1116 . Wang, H., Zaniolo, C., and Luo, C. 2003. ATLaS: A small but complete SQL extension for data mining and data streams. In Proceedings of the International Conference on Very Large Databases (VLDB), 1113--1116."},{"volume-title":"Proceedings of the International Conference on Data Engineering, 51--60","author":"Yang J.","key":"e_1_2_2_58_1","unstructured":"Yang , J. and Widom , J . 2001. Incremental computation and maintenance of temporal aggregates . In Proceedings of the International Conference on Data Engineering, 51--60 . Yang, J. and Widom, J. 2001. Incremental computation and maintenance of temporal aggregates. In Proceedings of the International Conference on Data Engineering, 51--60."},{"key":"e_1_2_2_59_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.43"},{"key":"e_1_2_2_60_1","doi-asserted-by":"publisher","DOI":"10.1145\/1007568.1007617"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1508857.1508861","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1508857.1508861","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T13:29:42Z","timestamp":1750253382000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1508857.1508861"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2009,4]]},"references-count":59,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,4]]}},"alternative-id":["10.1145\/1508857.1508861"],"URL":"https:\/\/doi.org\/10.1145\/1508857.1508861","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"type":"print","value":"0362-5915"},{"type":"electronic","value":"1557-4644"}],"subject":[],"published":{"date-parts":[[2009,4]]},"assertion":[{"value":"2007-04-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2008-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-04-23","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}