Extending Relational Query Languages for Data Streams | SpringerLink
Skip to main content
Springer Nature Link
Log in

Extending Relational Query Languages for Data Streams

  • Chapter
  • First Online:
Data Stream Management

Part of the book series: Data-Centric Systems and Applications ((DCSA))

Abstract

The design of continuous query languages for data streams and the extent to which these should rely on database query languages represent pivotal issues for data stream management systems (DSMSs). The Expressive Stream Language (ESL) of our Stream Mill system is designed to maximize the spectrum of applications a DSMS can support efficiently, while retaining compatibility with the SQL:2003 standards. This approach offers significant advantages, particularly for the many applications that span both data streams and databases. Therefore, ESL supports minimal extensions required to overcome SQL’s expressive power limitations—a critical enhancement since said limitations are quite severe on database applications and are further exacerbated on data stream applications, where, e.g., only nonblocking query operators can be used. Thus, ESL builds on user-defined aggregates and flexible window mechanisms to turn SQL into a powerful and computationally-complete query language, which is capable of supporting applications, such as data stream mining and sequence queries that are beyond the application scope of other DSMSs.

This is a preview of subscription content, log in via an institution to check access.

Access this chapter

Log in via an institution

Subscribe and save

Springer+ Basic
¥17,985 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Chapter
JPY 3498
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
eBook
JPY 7435
Price includes VAT (Japan)
  • Available as PDF
  • Read on any device
  • Instant download
  • Own it forever
Softcover Book
JPY 9294
Price includes VAT (Japan)
  • Compact, lightweight edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info
Hardcover Book
JPY 12869
Price includes VAT (Japan)
  • Durable hardcover edition
  • Dispatched in 3 to 5 business days
  • Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Purchases are for personal use only

Institutional subscriptions

Preview

Unable to display preview. Download preview PDF.

Unable to display preview. Download preview PDF.

Similar content being viewed by others

References

  1. D. Abadi, D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, M. Stonebraker, N. Tatbul, S.Z. Aurora, A new model and architecture for data stream management. VLDB J. 12(2), 120–139 (2003)

    Article  Google Scholar 

  2. C. Cortes, K. Fisher, D. Pregibon, A. Rogers, Hancock: a language for extracting signatures from data streams, in SIGKDD (2000), pp. 9–17

    Google Scholar 

  3. P. Felber, P. Eugster, R. Guerraoui, A. Kermarrec, The many faces of publish/subscribe. ACM Comput. Surv. 35(2), 114–131 (2003)

    Article  Google Scholar 

  4. ISO/IEC. Database languages—SQL, ISO/IEC 9075-*:2003 (2003)

    Google Scholar 

  5. B. Babcock, S. Babu, M. Datar, R. Motwani, J. Widom, Models and issues in data stream systems, in PODS (2002), pp. 1–16

    Google Scholar 

  6. Y.-N. Law, H. Wang, C. Zaniolo, Data models and query language for data streams, in VLDB (2004), pp. 492–503

    Google Scholar 

  7. I. Information Technologies, Illustra user’s guide, in 1111 Broadway, Suite 2000, Oakland, CA (1994)

    Google Scholar 

  8. D. Florescu, C. Hillery, D. Kossmann et al., The BEA/XQRL streaming xquery processor. VLDB J. 13(3), 294–315 (2004)

    Article  Google Scholar 

  9. Oracle. Oracle9i application developer’s guide advanced queuing. Oracle, Redwood Shores, CA, USA (2002)

    Google Scholar 

  10. H. Wang, C. Zaniolo, Using SQL to build new aggregates and extenders for object-relational systems, in VLDB (2000), pp. 166–175

    Google Scholar 

  11. H. Wang, C. Zaniolo, Atlas: a native extension of sql for data minining, in Proceedings of Third SIAM Int. Conference on Data Mining (2003), pp. 130–141

    Google Scholar 

  12. J. Li, D. Maier, K. Tufte, V. Papadimos, P.A. Tucker, Semantics and evaluation techniques for window aggregates in data streams, in SIGMOD Conference (2005), pp. 311–322

    Google Scholar 

  13. Stream mill home. http://wis.cs.ucla.edu/stream-mill

  14. A. Arasu, S. Babu, J. Widom, Cql: a language for continuous queries over streams and relations, in DBPL (2003), pp. 1–19

    Google Scholar 

  15. C. Cranor, Y. Gao, T. Johnson, V. Shkapenyuk, O. Spatscheck, Gigascope: high performance network monitoring with an sql interface, in SIGMOD (ACM, New York, 2002), p. 623

    Google Scholar 

  16. R. Sadri, C. Zaniolo, A. Zarkesh, J. Adibi, Optimization of sequence queries in database systems, in PODS (2001)

    Google Scholar 

  17. R. Sadri, C. Zaniolo, A.M. Zarkesh, J. Adibi, Expressing and optimizing sequence queries in database systems. ACM Trans. Database Syst. 29(2), 282–318 (2004)

    Article  Google Scholar 

  18. F. Zemke, A. Witkowski, M. Cherniak, L. Colby, Pattern matching in sequences of rows, in Sql Change Proposal (2007). http://www.sqlsnippets.com/en/topic-12162.html

    Google Scholar 

  19. N. Dindar, B. Güç, P. Lau, A. Ozal, M. Soner, N. Tatbul, Dejavu: declarative pattern matching over live and archived streams of events, in SIGMOD Conference (2009), pp. 1023–1026

    Google Scholar 

  20. E. Wu, Y. Diao, S. Rizvi, High-performance complex event processing over streams, in SIGMOD Conference (2006), pp. 407–418

    Google Scholar 

  21. D. Gyllstrom, J. Agrawal, Y. Diao, N. Immerman, On supporting kleene closure over event streams, in ICDE (2008), pp. 1391–1393

    Google Scholar 

  22. A.J. Demers et al., Cayuga: a high-performance event processing engine, in SIGMOD Conference (2007), pp. 1100–1102

    Google Scholar 

  23. R.S. Barga et al., Consistent streaming through time: a vision for event stream processing, in CIDR (2007), pp. 363–374

    Google Scholar 

  24. B. Mozafari, K. Zeng, C. Zaniolo, K*SQL: a unifying engine for sequence patterns and XML, in SIGMOD Conference–Demo Track (2010), pp. 1143–1146

    Google Scholar 

  25. B. Mozafari, K. Zeng, C. Zaniolo, From regular expressions to nested words: unifying languages and query execution for relational and XML sequences. Proc. VLDB Endow. 3(1), 150–161 (2010)

    Article  Google Scholar 

  26. R. Alur, P. Madhusudan, Adding nesting structure to words, in Developments in Language Theory (2006)

    Google Scholar 

  27. R. Alur, P. Madhusudan, Visibly pushdown languages, in STOC (2004), pp. 202–211

    Google Scholar 

  28. X. Zhou, H. Thakkar, C. Zaniolo, Unifying the processing of XML streams and relational data streams, in ICDE (2006), p. 50

    Google Scholar 

  29. U. Srivastava, J. Widom, Memory-limited execution of windowed stream joins, in VLDB (2004), pp. 324–335

    Google Scholar 

  30. Y. Bai, H. Thakkar, C. Luo, H. Wang, C. Zaniolo, A data stream language and system designed for power and flexibility, in CIKM (2006), pp. 337–346

    Google Scholar 

  31. L. Golab, M. Tamer Özsu, Update-pattern-aware modeling and processing of continuous queries, in ACM SIGMOD Conference (2005), pp. 658–669

    Google Scholar 

  32. B. Mozafari, C. Zaniolo, Optimal load shedding with aggregates and mining queries, in ICDE (2010), pp. 76–88

    Google Scholar 

  33. Y.-N. Law, C. Zaniolo, Improving the accuracy of continuous aggregates and mining queries on data streams under load shedding. Int. J. Bus. Intell. Data Min. 3(1), 99–117 (2008)

    Article  Google Scholar 

  34. M. Datar, A. Gionis, P. Indyk, R. Motwani, Maintaining stream statistics over sliding windows: (extended abstract), in Proceedings of the Thirteenth Annual ACM–SIAM Symposium on Discrete Algorithms (2002), pp. 635–644

    Google Scholar 

  35. C. Aggarwal, Data Streams: Models and Algorithms (Springer, Berlin, 2007)

    Book  MATH  Google Scholar 

  36. H. Mousavi, C. Zaniolo, Fast and accurate computation of equi-depth histograms over data streams, in EDBT (2011), pp. 69–80

    Google Scholar 

  37. C. Jin, W. Qian, C. Sha, J.X. Yu, A. Zhou, Dynamically maintaining frequent items over a data stream, in Proceedings of the 12th ACM Conference on Information and Knowledge Management (CIKM) (2003)

    Google Scholar 

  38. M. Charikar, K. Chen, M. Farach-Colton, Finding frequent items in data streams, in International Colloquium on Automata, Languages, and Programming (ICALP) (2000), pp. 508–515

    Google Scholar 

  39. G. Cormode, S. Muthukrishnan, What’s hot and what’s not: tracking most frequent items dynamically, in PODS (2003), pp. 296–306

    Google Scholar 

  40. H. Thakkar, N. Laptev, H. Mousavi, B. Mozafari, V. Russo, S.M.M. Carlo Zaniolo, A data stream management system for knowledge discovery, in ICDE (2011), pp. 757–768

    Google Scholar 

  41. S. Sarawagi, S. Thomas, R. Agrawal, Integrating association rule mining with relational database systems: alternatives and implications, in SIGMOD (1998)

    Google Scholar 

  42. T. Imielinski, H. Mannila, A database perspective on knowledge discovery. Commun. ACM 39(11), 58–64 (1996)

    Article  Google Scholar 

  43. C. Zaniolo, Mining databases and data streams with query languages and rules—invited paper, in KDID 2005: Knowledge Discovery in Inductive Databases, 4th International Workshop. Lecture Notes in Computer Science, vol. 3933 (Springer, Berlin, 2006), pp. 24–37

    Google Scholar 

  44. Z. Tang, J. Maclennan, P.P. Kim, Building data mining solutions with OLE DB for DM and XML for analysis. SIGMOD Rec. 34(2), 80–85 (2005)

    Article  Google Scholar 

  45. H. Thakkar, B. Mozafari, C. Zaniolo, Designing an inductive data stream management system: the stream Mill experience, in SSPS (2008), pp. 79–88

    Chapter  Google Scholar 

  46. H.-P. Kriegel, M. Ester, J. Sander, X. Xu, A density-based algorithm for discovering clusters in large spatial databases with noise, in KDD (1996), pp. 226–231

    Google Scholar 

  47. H. Wang Wei Fan, P.S. Yu, J. Han, Mining concept-drifting data streams using ensemble classifiers, in KDD (2003), pp. 226–235

    Google Scholar 

  48. B. Mozafari, H. Thakkar, C. Zaniolo, Verifying and mining frequent patterns from large windows over data streams, in ICDE (2008), pp. 179–188

    Google Scholar 

  49. A. Bifet, G. Holmes, B. Pfahringer, P. Kranen, H. Kremer, T. Jansen, T. Seidl, Moa: massive online analysis, a framework for stream classification and clustering. J. Mach. Learn. Res. 11, 44–50 (2010)

    Google Scholar 

  50. Y. Bai, C. Zaniolo, Minimizing latency and memory in DSMS: a unified approach to quasi-optimal scheduling, in SSPS (2008), pp. 58–67

    Chapter  Google Scholar 

  51. Y. Bai, H. Thakkar, H. Wang, C. Zaniolo, Optimizing timestamp management in data stream management systems, in ICDE (2007), pp. 1334–1338

    Google Scholar 

  52. L. Golab, M. Tamer Özsu, Issues in data stream management. ACM SIGMOD Rec. 32(2), 5–14 (2003)

    Article  MATH  Google Scholar 

  53. D. Barbara, The characterization of continuous queries. Int. J. Coop. Inf. Syst. 8(4), 295–323 (1999)

    Article  Google Scholar 

  54. D.B. Terry, D. Goldberg, D.A. Nichols, B.M. Oki, Continuous queries over append-only databases, in SIGMOD Conference (1992), pp. 321–330

    Google Scholar 

  55. M. Sullivan, Tribeca: a stream database manager for network traffic analysis, in VLDB (1996), p. 594

    Google Scholar 

  56. S. Chandrasekaran et al., TelegraphCQ: continuous dataflow processing for an uncertain world, in CIDR (2003)

    Google Scholar 

  57. L. Liu, C. Pu, W. Tang, Continual queries for Internet scale event-driven information delivery. IEEE Trans. Knowl. Data Eng. 11(4), 583–590 (1999)

    Google Scholar 

  58. J. Chen, D.J. DeWitt, F. Tian, Y. Wang, NiagaraCQ: a scalable continuous query system for Internet databases, in SIGMOD (2000), pp. 379–390

    Chapter  Google Scholar 

  59. H. Jagadish, I. Mumick, A. Silberschatz, View maintenance issues for the chronicle data model, in PODS (1995), pp. 113–124

    Google Scholar 

  60. A. Kumar Gupta, D. Suciu, Stream processing of xpath queries with predicates, in SIGMOD Conference (2003), pp. 419–430

    Google Scholar 

  61. D. Carney, U. Cetintemel, M. Cherniack, C. Convey, S. Lee, G. Seidman, M. Stonebraker, N. Tatbul, S. Zdonik, Monitoring streams—a new class of data management applications, in VLDB, Hong Kong, China (2002)

    Google Scholar 

  62. Y.-N. Law, H. Wang, C. Zaniolo, Relational languages and data models for continuous queries on sequences and data streams. ACM Trans. Database Syst. 36, 8 (2011)

    Article  Google Scholar 

  63. C. Luo, H. Thakkar, H. Wang, C. Zaniolo, A native extension of SQL for mining data streams, in ACM SIGMOD Conference 2005 (2005), pp. 873–875

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. Computer Science Department, University of California, Los Angeles, CA, 90095, USA

    N. Laptev, B. Mozafari, H. Mousavi, K. Zeng & Carlo Zaniolo

  2. Google Inc., Mountain View, CA, 94043, USA

    H. Thakkar

  3. Sigma Center, Microsoft Research Asia, Beijing, 100190, P.R. China

    H. Wang

Authors
  1. N. Laptev
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. B. Mozafari
    View author publications

    You can also search for this author in PubMed Google Scholar

  3. H. Mousavi
    View author publications

    You can also search for this author in PubMed Google Scholar

  4. H. Thakkar
    View author publications

    You can also search for this author in PubMed Google Scholar

  5. H. Wang
    View author publications

    You can also search for this author in PubMed Google Scholar

  6. K. Zeng
    View author publications

    You can also search for this author in PubMed Google Scholar

  7. Carlo Zaniolo
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Carlo Zaniolo .

Editor information

Editors and Affiliations

  1. University Campus - Kounoupidiana, School of ECE, Techn. Univ. of Crete University Campus - Kounoupidiana, Chania, Greece

    Minos Garofalakis

  2. Microsoft Corporation, Redmond, Washington, USA

    Johannes Gehrke

  3. Amazon India , Bangalore, India

    Rajeev Rastogi

Rights and permissions

Reprints and permissions

Copyright information

© 2016 Springer-Verlag Berlin Heidelberg

About this chapter

Cite this chapter

Laptev, N. et al. (2016). Extending Relational Query Languages for Data Streams. In: Garofalakis, M., Gehrke, J., Rastogi, R. (eds) Data Stream Management. Data-Centric Systems and Applications. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-540-28608-0_18

Download citation

  • DOI: https://doi.org/10.1007/978-3-540-28608-0_18

  • Published:

  • Publisher Name: Springer, Berlin, Heidelberg

  • Print ISBN: 978-3-540-28607-3

  • Online ISBN: 978-3-540-28608-0

  • eBook Packages: Computer ScienceComputer Science (R0)

Publish with us

Policies and ethics