Skip to main content
Fachgebiete
Automobil + Motoren Bauwesen + Immobilien Business IT + Informatik Elektrotechnik + Elektronik Energie + Nachhaltigkeit Finance + Banking Management + Führung Marketing + Vertrieb Maschinenbau + Werkstoffe Versicherung + Risiko
DE
EN
Bücher
Zeitschriften
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
SLX-Digitalkonferenz: Zukunftswerkstatt 2024

Mehr Umsatz mit Top-Kontakten

Am 7. Mai erfahren Sie, wie Vertriebsteams Leadgenerierung, Leadnurturing und Leadstrategien effizient steuern können.
Erweiterte Suche
Anmelden
nach oben
The VLDB Journal
Erschienen in: The VLDB Journal 2/2014

01.04.2014 | Special Issue Paper

DBToaster: higher-order delta processing for dynamic, frequently fresh views

verfasst von: Christoph Koch, Yanif Ahmad, Oliver Kennedy, Milos Nikolic, Andres Nötzli, Daniel Lupei, Amir Shaikhha

Erschienen in: The VLDB Journal | Ausgabe 2/2014

Einloggen

Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.

search-config
loading …

Abstract

Applications ranging from algorithmic trading to scientific data analysis require real-time analytics based on views over databases receiving thousands of updates each second. Such views have to be kept fresh at millisecond latencies. At the same time, these views have to support classical SQL, rather than window semantics, to enable applications that combine current with aged or historical data. In this article, we present the DBToaster system, which keeps materialized views of standard SQL queries continuously fresh as data changes very rapidly. This is achieved by a combination of aggressive compilation techniques and DBToaster’s original recursive finite differencing technique which materializes a query and a set of its higher-order deltas as views. These views support each other’s incremental maintenance, leading to a reduced overall view maintenance cost. DBToaster supports tens of thousands of complete view refreshes per second for a wide range of queries.
Vorheriger Artikel Efficient processing of -hop reachability queries
Nächster Artikel Quantifying eventual consistency with PBS

Sie haben noch keine Lizenz? Dann Informieren Sie sich jetzt über unsere Produkte:

Springer Professional "Wirtschaft+Technik"

Online-Abonnement

Mit Springer Professional "Wirtschaft+Technik" erhalten Sie Zugriff auf:

  • über 102.000 Bücher
  • über 537 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Maschinenbau + Werkstoffe
  • Versicherung + Risiko

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Technik"

Online-Abonnement

Mit Springer Professional "Technik" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 390 Zeitschriften

aus folgenden Fachgebieten:

  • Automobil + Motoren
  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Elektrotechnik + Elektronik
  • Energie + Nachhaltigkeit
  • Maschinenbau + Werkstoffe




 

Jetzt Wissensvorsprung sichern!

Jetzt informieren

Springer Professional "Wirtschaft"

Online-Abonnement

Mit Springer Professional "Wirtschaft" erhalten Sie Zugriff auf:

  • über 67.000 Bücher
  • über 340 Zeitschriften

aus folgenden Fachgebieten:

  • Bauwesen + Immobilien
  • Business IT + Informatik
  • Finance + Banking
  • Management + Führung
  • Marketing + Vertrieb
  • Versicherung + Risiko




Jetzt Wissensvorsprung sichern!

Jetzt informieren
Fußnoten
1
In the sense of higher-order derivative, not higher-order function.
 
2
Note that the operation need not actually have a sum aggregate. An expression \(Q\) with output variables \(\vec {A}\) is equivalent to the expression \({\hbox {Sum}_{\vec {A}}}(Q)\).
 
3
The detailed queries can be found in our technical report [24] or on our Web site http://​www.​dbtoaster.​org.
 
4
Q17, Q17a produce incorrect results due to floating point errors.
 
Literatur
1.
Abadi, D., Ahmad, Y., Balazinska, M., Cetintemel, U., Cherniack, M., Hwang, J., Lindner, W., Maskey, A., Rasin, A., Ryvkina, E., et al.: The design of the Borealis stream processing engine. In: CIDR, pp. 277–289 (2005)
2.
Agrawal, S., Chaudhuri, S., Narasayya, V.R.: Automated selection of materialized views and indexes in SQL databases. In: VLDB, pp. 496–505 (2000)
3.
Ahmad, Y., Koch, C.: DBToaster: A SQL compiler for high-performance delta processing in main-memory databases. PVLDB 2(2), 1566–1569 (2009)
4.
Aiken, A., Hellerstein, J.M., Widom, J.: Static analysis techniques for predicting the behavior of active database rules. ACM TODS 20(1), 3–41 (1995)CrossRef
5.
6.
Blakeley, J.A., Larson, P.Å., Tompa, F.W.: Efficiently updating materialized views. In: SIGMOD, pp. 61–71 (1986)
7.
Buneman, P., Clemons, E.K.: Efficiently monitoring relational databases. ACM TODS 4(3), 368–382 (1979)
8.
Buneman, P., Naqvi, S.A., Tannen, V., Wong, L.: Principles of programming with complex objects and collection types. Theor. Comput. Sci. 149(1), 3–48 (1995)CrossRefMATHMathSciNet
9.
Chaudhuri, S., Krishnamurthy, R., Potamianos, S., Shim, K.: Optimizing queries with materialized views. In: ICDE, pp. 190–200 (1995)
10.
Chirkova, R., Yang, J.: Materialized views. Found. Trends Databases 4(4), 295–405 (2012)CrossRef
11.
Colby, L.S., Griffin, T., Libkin, L., Mumick, I.S., Trickey, H.: Algorithms for deferred view maintenance. In: SIGMOD, pp. 469–480 (1996)
12.
Colby, L.S., Kawaguchi, A., Lieuwen, D.F., Mumick, I.S., Ross, K.A.: Supporting multiple view maintenance policies. In: SIGMOD, pp. 405–416 (1997)
13.
Cormode, G., Muthukrishnan, S.: What’s hot and what’s not: tracking most frequent items dynamically. ACM TODS 30(1), 249–278 (2005)CrossRefMathSciNet
14.
15.
Ghanem, T.M., Elmagarmid, A.K., Larson, P.Å., Aref, W.G.: Supporting views in data stream management systems. ACM TODS 35(1), 1–47 (2010)CrossRef
16.
Griffin, T., Libkin, L.: Incremental maintenance of views with duplicates. In: SIGMOD, pp. 328–339 (1995)
17.
Gupta, A., Mumick, I.S., Subrahmanian, V.S.: Maintaining views incrementally. In: SIGMOD, pp. 157–166 (1993)
18.
Gupta, H., Mumick, I.S.: Selection of views to materialize in a data warehouse. IEEE TKDE 17(1), 24–43 (2005)
19.
Kawaguchi, A., Lieuwen, D.F., Mumick, I.S., Ross, K.A.: Implementing incremental view maintenance in nested data models. In: DBPL, pp. 202–221 (1997)
20.
Kearns, M., Ortiz, L.: The Penn-Lehman automated trading project. IEEE Intell. Syst. 18(6), 22–31 (2003)CrossRef
21.
Kennedy, O., Ahmad, Y., Koch, C.: DBToaster: Agile views for a dynamic data management system. In: CIDR, pp. 284–295 (2011)
22.
Koch, C.: Incremental query evaluation in a ring of databases. In: PODS, pp. 87–98 (2010)
23.
24.
Koch, C., Ahmad, Y., Kennedy, O., Nikolic, M., Nötzli, A., Lupei, D., Shaikhha, A.: Dbtoaster: Higher-order delta processing for dynamic, frequently fresh views (2013). Technical report EPFL-REPORT-183767, extends this article by an appendix that lists the full query workload as well as experimental parameters and trace figures that did not find space in this article; http://​infoscience.​epfl.​ch/​record/​183767
25.
Kotidis, Y., Roussopoulos, N.: A case for dynamic view management. ACM TODS 26(4), 388–423 (2001)
26.
Krikellas, K., Viglas, S., Cintra, M.: Generating code for holistic query evaluation. In: ICDE (2010)
27.
Krishnamurthy, S., Wu, C., Franklin, M.J.: On-the-fly sharing for streamed aggregation. In: SIGMOD, pp. 623–634 (2006)
28.
Larson, P.Å., Zhou, J.: Efficient maintenance of materialized outer-join views. In: ICDE, pp. 56–65 (2007)
29.
Liu, Y.A., Stoller, S.D., Teitelbaum, T.: Static caching for incremental computation. ACM TOPLAS 20(3), 546–585 (1998)CrossRef
30.
Marlow, S., Wadler, P.: Deforestation for higher-order functions. In: Functional Programming, pp. 154–165 (1992)
31.
Motwani, R., Widom, J., Arasu, A., Babcock, B., Babu, S., Datar, M., Manku, G.S., Olston, C., Rosenstein, J., Varma, R.: Query processing, approximation, and resource management in a data stream management system. In: CIDR (2003)
32.
Neumann, T.: Efficiently compiling efficient query plans for modern hardware. PVLDB 4(9), 539–550 (2011)
33.
Nutanong, S., Carey, N., Ahmad, Y., Szalay, A.S., Woolf, T.B.: Adaptive exploration for large-scale protein analysis in the molecular dynamics database. In: SSDBM, p. 45 (2013)
34.
Palpanas, T., Sidle, R., Cochrane, R., Pirahesh, H.: Incremental maintenance for non-distributive aggregate functions. In: VLDB, pp. 802–813 (2002)
35.
Pearlmutter, B.A., Siskind, J.M.: Lazy multivariate higher-order forward-mode AD. In: POPL, pp. 155–160 (2007)
36.
Ross, K.A., Srivastava, D., Sudarshan, S.: Materialized view maintenance and integrity constraint checking: trading space for time. In: SIGMOD, pp. 447–458 (1996)
37.
Roussopoulos, N.: An incremental access method for ViewCache: concept, algorithms, and cost analysis. ACM TODS 16(3), 535–563 (1991)CrossRef
38.
Salem, K., Beyer, K.S., Cochrane, R., Lindsay, B.G.: How to roll a join: Asynchronous incremental view maintenance. In: SIGMOD, pp. 129–140 (2000)
39.
Seshadri, P., Pirahesh, H., Leung, T.C.: Complex query decorrelation. In: ICDE, pp. 450–458. IEEE (1996)
40.
Shyamshankar, P., Palmer, Z., Ahmad, Y.: K3: Language design for building multi-platform, domain-specific runtimes. In: International Workshop on Cross-model Language Design and Implementation (XLDI) (2012)
41.
Tatbul, N., Çetintemel, U., Zdonik, S.B., Cherniack, M., Stonebraker, M.: Load shedding in a data stream manager. In: VLDB, pp. 309–320 (2003)
42.
43.
Wong, L.: Kleisli, a functional query system. J. Funct. Program. 10(1), 19–56 (2000)CrossRef
44.
Yang, J., Widom, J.: Incremental computation and maintenance of temporal aggregates. VLDB J. 12(3), 262–283 (2003)CrossRef
45.
Zhou, J., Larson, P.Å., Elmongui, H.G.: Lazy maintenance of materialized views. In: VLDB, pp. 231–242 (2007)
46.
Zhou, J., Larson, P.Å., Freytag, J.C., Lehner, W.: Efficient exploitation of similar subexpressions for query processing. In: SIGMOD, pp. 533–544 (2007)
47.
Zilio, D.C., Zuzarte, C., Lightstone, S., Ma, W., Lohman, G.M., Cochrane, R., Pirahesh, H., Colby, L.S., Gryz, J., Alton, E., Liang, D., Valentin, G.: Recommending materialized views and indexes with IBM DB2 design advisor. In: ICAC, pp. 180–188 (2004)
Metadaten
Titel
DBToaster: higher-order delta processing for dynamic, frequently fresh views
verfasst von
Christoph Koch
Yanif Ahmad
Oliver Kennedy
Milos Nikolic
Andres Nötzli
Daniel Lupei
Amir Shaikhha
Publikationsdatum
01.04.2014
Verlag
Springer Berlin Heidelberg
Erschienen in
The VLDB Journal / Ausgabe 2/2014
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-013-0348-4

Weitere Artikel der Ausgabe 2/2014

The VLDB Journal 2/2014 Zur Ausgabe

Special Issue Paper

Dense subgraph maintenance under streaming edge weight updates for real-time story identification

Special Issue Paper

Quantifying eventual consistency with PBS

Special Issue Paper

Toward cost-effective storage provisioning for DBMSs

Guest Editorial

Special issue on best papers of VLDB 2012

Special Issue Paper

Efficient processing of -hop reachability queries

Special Issue Paper

Transactional support for adaptive indexing

Premium Partner

    Bildnachweise