Skip to main content

2017 | OriginalPaper | Buchkapitel

Querying Graph Databases: What Do Graph Patterns Mean?

verfasst von : Stephan Mennicke, Jan-Christoph Kalo, Wolf-Tilo Balke

Erschienen in: Conceptual Modeling

Verlag: Springer International Publishing

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

search-config
loading …

Abstract

Querying graph databases often amounts to some form of graph pattern matching. Finding (sub-)graphs isomorphic to a given graph pattern is common to many graph query languages, even though graph isomorphism often is too strict, since it requires a one-to-one correspondence between the nodes of the pattern and that of a match. We investigate the influence of weaker graph pattern matching relations on the respective queries they express. Thereby, these relations abstract from the concrete graph topology to different degrees. An extension of relation sequences, called failures which we borrow from studies on concurrent processes, naturally expresses simple presence conditions for relations and properties. This is very useful in application scenarios dealing with databases with a notion of data completeness. Furthermore, failures open up the query modeling for more intricate matching relations directly incorporating concrete data values.

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!

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!

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!

Literatur
1.
Zurück zum Zitat Abriola, S., Barceió, P., Figueira, D., Figueira, S.: Bisimulations on data graphs. In: KR 2016, pp. 309–318. AAAI Press (2016) Abriola, S., Barceió, P., Figueira, D., Figueira, S.: Bisimulations on data graphs. In: KR 2016, pp. 309–318. AAAI Press (2016)
2.
Zurück zum Zitat Angles, R., Gutierrez, C.: Querying RDF data from a graph database perspective. In: Gómez-Pérez, A., Euzenat, J. (eds.) ESWC 2005. LNCS, vol. 3532, pp. 346–360. Springer, Heidelberg (2005). doi:10.1007/11431053_24CrossRef Angles, R., Gutierrez, C.: Querying RDF data from a graph database perspective. In: Gómez-Pérez, A., Euzenat, J. (eds.) ESWC 2005. LNCS, vol. 3532, pp. 346–360. Springer, Heidelberg (2005). doi:10.​1007/​11431053_​24CrossRef
3.
Zurück zum Zitat Brookes, S.D., Hoare, C.A.R., Roscoe, A.W.: A theory of communicating sequential processes. J. ACM 31(3), 560–599 (1984)MathSciNetCrossRef Brookes, S.D., Hoare, C.A.R., Roscoe, A.W.: A theory of communicating sequential processes. J. ACM 31(3), 560–599 (1984)MathSciNetCrossRef
4.
Zurück zum Zitat Brynielsson, J., Högberg, J., Kaati, L., Mårtenson, C., Svenson, P.: Detecting social positions using simulation. In: ASONAM 2010, pp. 48–55 (2010) Brynielsson, J., Högberg, J., Kaati, L., Mårtenson, C., Svenson, P.: Detecting social positions using simulation. In: ASONAM 2010, pp. 48–55 (2010)
5.
Zurück zum Zitat Fan, W.: Graph pattern matching revised for social network analysis. In: ICDT 2012, pp. 8–21. ACM, New York (2012) Fan, W.: Graph pattern matching revised for social network analysis. In: ICDT 2012, pp. 8–21. ACM, New York (2012)
6.
Zurück zum Zitat Fan, W., Li, J., Ma, S., Tang, N., Wu, Y., Wu, Y.: Graph pattern matching: from intractable to polynomial time. PVLDB Endow. 3(1–2), 264–275 (2010)CrossRef Fan, W., Li, J., Ma, S., Tang, N., Wu, Y., Wu, Y.: Graph pattern matching: from intractable to polynomial time. PVLDB Endow. 3(1–2), 264–275 (2010)CrossRef
7.
Zurück zum Zitat Gallagher, B.: Matching structure and semantics: a survey on graph-based pattern matching. In: Papers from the AAAI FS 2006, pp. 45–53 (2006) Gallagher, B.: Matching structure and semantics: a survey on graph-based pattern matching. In: Papers from the AAAI FS 2006, pp. 45–53 (2006)
8.
Zurück zum Zitat van Glabbeek, R.J.: The linear time - branching time spectrum. In: Baeten, J.C.M., Klop, J.W. (eds.) CONCUR 1990. LNCS, vol. 458, pp. 278–297. Springer, Heidelberg (1990). doi:10.1007/BFb0039066CrossRef van Glabbeek, R.J.: The linear time - branching time spectrum. In: Baeten, J.C.M., Klop, J.W. (eds.) CONCUR 1990. LNCS, vol. 458, pp. 278–297. Springer, Heidelberg (1990). doi:10.​1007/​BFb0039066CrossRef
9.
Zurück zum Zitat Henzinger, M., Henzinger, T., Kopke, P.: Computing simulations on finite and infinite graphs. In: FOCS 1995, pp. 453–462. IEEE Computer Society (1995) Henzinger, M., Henzinger, T., Kopke, P.: Computing simulations on finite and infinite graphs. In: FOCS 1995, pp. 453–462. IEEE Computer Society (1995)
10.
Zurück zum Zitat Imielinski, T., Lipski Jr., W.: Incomplete information in relational databases. J. ACM 31(4), 761–791 (1984)MathSciNetCrossRef Imielinski, T., Lipski Jr., W.: Incomplete information in relational databases. J. ACM 31(4), 761–791 (1984)MathSciNetCrossRef
11.
Zurück zum Zitat Khan, A., Wu, Y., Aggarwal, C.C., Yan, X.: NeMa: fast graph search with label similarity. PVLDB Endow. 6(3), 181–192 (2013)CrossRef Khan, A., Wu, Y., Aggarwal, C.C., Yan, X.: NeMa: fast graph search with label similarity. PVLDB Endow. 6(3), 181–192 (2013)CrossRef
12.
Zurück zum Zitat Lee, J., Han, W.S., Kasperovics, R., Lee, J.H.: An in-depth comparison of subgraph isomorphism algorithms in graph databases. PVLDB Endow. 6(2), 133–144 (2012)CrossRef Lee, J., Han, W.S., Kasperovics, R., Lee, J.H.: An in-depth comparison of subgraph isomorphism algorithms in graph databases. PVLDB Endow. 6(2), 133–144 (2012)CrossRef
13.
Zurück zum Zitat Libkin, L., Martens, W., Vrgoč, D.: Querying graph databases with XPath. In: ICDT 2013, pp. 129–140. ACM, New York (2013) Libkin, L., Martens, W., Vrgoč, D.: Querying graph databases with XPath. In: ICDT 2013, pp. 129–140. ACM, New York (2013)
14.
15.
Zurück zum Zitat Ma, S., Cao, Y., Fan, W., Huai, J., Wo, T.: Strong simulation: capturing topology in graph pattern matching. ACM Trans. Database Syst. 39(1), 4:1–4:46 (2014)MathSciNetCrossRef Ma, S., Cao, Y., Fan, W., Huai, J., Wo, T.: Strong simulation: capturing topology in graph pattern matching. ACM Trans. Database Syst. 39(1), 4:1–4:46 (2014)MathSciNetCrossRef
16.
Zurück zum Zitat Motik, B., Horrocks, I., Sattler, U.: Bridging the gap between OWL and relational databases. In: WWW 2007, pp. 807–816. ACM, New York (2007) Motik, B., Horrocks, I., Sattler, U.: Bridging the gap between OWL and relational databases. In: WWW 2007, pp. 807–816. ACM, New York (2007)
17.
Zurück zum Zitat Mottin, D., Lissandrini, M., Velegrakis, Y., Palpanas, T.: Exemplar queries: a new way of searching. VLDB J. 25(6), 741–765 (2016)CrossRef Mottin, D., Lissandrini, M., Velegrakis, Y., Palpanas, T.: Exemplar queries: a new way of searching. VLDB J. 25(6), 741–765 (2016)CrossRef
18.
Zurück zum Zitat Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Efficient graph similarity search over large graph databases. IEEE Trans. Knowl. Data Eng. 27(4), 964–978 (2015)CrossRef Zheng, W., Zou, L., Lian, X., Wang, D., Zhao, D.: Efficient graph similarity search over large graph databases. IEEE Trans. Knowl. Data Eng. 27(4), 964–978 (2015)CrossRef
19.
Zurück zum Zitat Zheng, W., Zou, L., Peng, W., Yan, X., Song, S., Zhao, D.: Semantic SPARQL similarity search over RDF knowledge graphs. PVLDB Endow. 9(11), 840–851 (2016)CrossRef Zheng, W., Zou, L., Peng, W., Yan, X., Song, S., Zhao, D.: Semantic SPARQL similarity search over RDF knowledge graphs. PVLDB Endow. 9(11), 840–851 (2016)CrossRef
Metadaten
Titel
Querying Graph Databases: What Do Graph Patterns Mean?
verfasst von
Stephan Mennicke
Jan-Christoph Kalo
Wolf-Tilo Balke
Copyright-Jahr
2017
DOI
https://doi.org/10.1007/978-3-319-69904-2_11