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
Themenseiten
Organisationspsychologie Projektmanagement Marketing Smart Manufacturing
Bücher
Zeitschriften
Weitere Formate
Podcasts Webinare Technik Webinare Wirtschaft Kongresse Veranstaltungskalender Awards
Jetzt Einzelzugang starten
Zugang für Unternehmen
Referenzkunden
MTZ-Fachkongress

Antriebe und Energiesysteme von morgen


Austausch von Automobil- und Energiewirtschaft

Am 14./15. Mai geht es in Chemnitz um die Mobilitätswende durch Elektro- und Wasserstofffahrzeuge.
Erweiterte Suche
Anmelden
nach oben
The VLDB Journal
Erschienen in: The VLDB Journal 3/2014

01.06.2014 | Regular Paper

The backchase revisited

verfasst von: Michael Meier

Erschienen in: The VLDB Journal | Ausgabe 3/2014

Einloggen

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

search-config
loading …

Abstract

Semantic query optimization is the process of finding equivalent rewritings of an input query given constraints that hold in a database instance. In this paper, we report about a Chase & Backchase (C&B) algorithm strategy that generalizes and improves on well-known methods in the field. The implementation of our approach, the Pegasussystem, outperforms existing C&B systems an average by two orders of magnitude. This gain in performance is due to a combination of novel methods that lower the complexity in practical situations significantly.
Vorheriger Artikel Towards zero-overhead static and adaptive indexing in Hadoop

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
Anhänge
Nur mit Berechtigung zugänglich
Fußnoten
1
In fact, for the scenarios with chain-star and chain queries OCS can decompose the constraint sets in two strata each but this does not speed up the overall computation.
 
Literatur
1.
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)MATH
2.
3.
Buneman, P., Fan, W., Weinstein, S.: Interaction between path and type constraints. ACM Trans. Comput. Logic 4(4), 530–577 (2003)CrossRefMathSciNet
4.
Calvanese, D., Giacomo, G., Lembo, D., Lenzerini, M., Rosati, R.: Tractable reasoning and efficient query answering in description logics: the DL-lite family. J. Autom. Reason. 39(3), 385–429 (2007)CrossRefMATH
5.
Chakravarthy, U.S., Grant, J., Minker, J.: Logic-based approach to semantic query optimization. ACM Trans. Database Syst. 15(2), 162–207 (1990)CrossRef
6.
Chandra, A.K., Merlin, P.M.: Optimal Implementation of Conjunctive Queries in Relational Databases. In: STOC, pp. 77–90 (1977)
7.
Damaggio, E., Deutsch, A., Vianu, V.: Artifact systems with data dependencies and arithmetic. In: ICDT, pp. 66–77 (2011)
8.
Deutsch, A., Nash, A., Remmel, J.: The chase revisited. In: PODS, pp. 149–158 (2008)
9.
Deutsch, A., Popa, L., Tannen, V.: Physical data independence, constraints, and optimization with universal plans. In: VLDB ’99, pp. 459–470 (1999)
10.
Deutsch, A., Tannen, V.: MARS: a system for publishing XML from mixed and redundant storage. In: VLDB, pp. 201–212 (2003)
11.
Deutsch, A.: Fol modeling of integrity constraints (dependencies). In: Encyclopedia of Database Systems, pp. 1155–1161. Springer, US (2009)
12.
Deutsch, A.: XML query reformulation over mixed and redundant storage. Ph.D. thesis, UPenn (2002)
13.
Deutsch, A., Tannen, V.: XML queries and constraints, containment and reformulation. Theor. Comput. Sci. 336(1), 57–87 (2005)CrossRefMATHMathSciNet
14.
Deutsch, A., Popa, L., Tannen, V.: Query reformulation with constraints. SIGMOD Rec. 35(1), 65–73 (2006)CrossRef
15.
Deutsch, A., Ludäscher, B., Nash, A.: Rewriting queries using views with access patterns under integrity constraints. Theor. Comput. Sci. 371(3), 200–226 (2007)CrossRefMATH
16.
Dong, G., Su, J.: Conjunctive query containment with respect to views and constraints. Inf. Process. Lett. 57(2), 95–102 (1996)CrossRefMATHMathSciNet
17.
Eiter, T., Ortiz, M., Simkus, M., Tran, T.K., Xiao, G.: Query rewriting for horn-shiq plus rules. In: AAAI (2012)
18.
19.
Fagin, R., Kolaitis, P.G., Miller, R.J., Popa, L.: Data exchange: semantics and query answering. Theor. Comput. Sci. 336(1), 89–124 (2005)CrossRefMATHMathSciNet
20.
Fuxman, A., Kolaitis, P.G., Miller, R.J., Tan, W.C.: Peer data exchange. In: PODS, pp. 160–171 (2005)
21.
22.
Greco, S., Spezzano, F., Trubitsyna, I.: Stratification criteria and rewriting techniques for checking chase termination. PVLDB 4(11), 1158–1168 (2011)
23.
Halevy, A.Y.: Answering queries using views: a survey. VLDB J. 10(4), 270–294 (2001)CrossRefMATH
24.
Hariri, B.B., Calvanese, D., Giacomo, G.D., Deutsch, A., Montali, M.: Verification of relational data-centric dynamic systems with external services. CoRR abs/1203.0024 (2012)
25.
Johnson, D.S., Klug, A.C.: Testing containment of conjunctive queries under functional and inclusion dependencies. J. Comput. Syst. Sci. 28(1), 167–189 (1984)CrossRefMATHMathSciNet
26.
Kikot, S., Kontchakov, R., Zakharyaschev, M.: Conjunctive query answering with owl 2 ql. In: KR (2012)
27.
King, J.J.: QUIST: a system for semantic query optimization in relational databases. Distributed systems, vol. II: distributed data base systems pp. 287–294 (1986)
28.
Lenzerini, M.: Data integration: a theoretical perspective. In: PODS, pp. 233–246 (2002)
29.
Maier, D., Mendelzon, A.O., Sagiv, Y.: Testing implications of data dependencies. ACM Trans. Database Syst. 4(4), 455–469 (1979)CrossRef
30.
Marnette, B.: Generalized schema-mappings: from termination to tractability. In: PODS, pp. 13–22 (2009)
31.
Meier, M., Schmidt, M., Lausen, G.: On chase termination beyond stratification. CoRR abs/0906.4228 (2009)
32.
Meier, M., Schmidt, M., Lausen, G.: Stop the chase, Technical Report. CoRR abs/0901.3984 (2009)
33.
Meier, M., Schmidt, M., Lausen, G.: On chase termination beyond stratification. PVLDB 2(1), 970–981 (2009)
34.
Meier, M., Schmidt, M., Wei, F., Lausen, G.: Semantic query optimization in the presence of types. J. Comput. Syst. Sci. 79(6), 937–957 (2013)CrossRefMATHMathSciNet
35.
Olteanu, D., Huang, J., Koch, C.: SPROUT:lazy vs. eager query plans for tuple-independent probabilistic databases. In: ICDE, pp. 640–651 (2009)
36.
Pérez-Urbina, H., Horrocks, I., Motik, B.: Efficient query answering for owl 2. In: International Semantic Web Conference, pp. 489–504 (2009)
37.
Pichler, R., Savenkov, V.: Towards practical feasibility of core computation in data exchange. Theor. Comput. Sci. 411(7–9), 935–957 (2010)CrossRefMATHMathSciNet
38.
Popa, L., Deutsch, A., Sahuguet, A., Tannen, V.: A chase too far? In: SIGMOD, pp. 273–284 (2000)
39.
Popa, L., Tannen, V.: An equational chase for path-conjunctive queries, constraints, and views. In: ICDT, pp. 39–57 (1999)
40.
Popa, L.: Object/relational query optimization with chase and backchase. Ph.D. thesis, UPenn (2000)
41.
Spezzano, F., Greco, S.: Chase termination: a constraints rewriting approach. PVLDB 3(1), 93–104 (2010)
Metadaten
Titel
The backchase revisited
verfasst von
Michael Meier
Publikationsdatum
01.06.2014
Verlag
Springer Berlin Heidelberg
Erschienen in
The VLDB Journal / Ausgabe 3/2014
Print ISSN: 1066-8888
Elektronische ISSN: 0949-877X
DOI
https://doi.org/10.1007/s00778-013-0333-y

Weitere Artikel der Ausgabe 3/2014

The VLDB Journal 3/2014 Zur Ausgabe

Regular Paper

A survey of large-scale analytical query processing in MapReduce

Regular Paper

Approximate similarity search for online multimedia services on distributed CPU–GPU platforms

Regular Paper

Towards zero-overhead static and adaptive indexing in Hadoop

Regular Paper

QUBLE: towards blending interactive visual subgraph search queries on large networks

Regular Paper

Personalized trajectory matching in spatial networks

Regular Paper

Event detection over twitter social media streams

Premium Partner

    Bildnachweise