Graph Query Processing | SpringerLink
Skip to main content
Springer Nature Link
Log in

Graph Query Processing

  • Living reference work entry
  • First Online:
Encyclopedia of Big Data Technologies

  • 512 Accesses

Definition

While being eminently useful in a wide variety of application domains, the high expressiveness of graph queries makes them hard to optimize and, hence, challenging to process efficiently. We discuss a number of state-of-the-art approaches which aim to overcome these challenges, focusing specifically on planning, optimization, and execution of two commonly used types of declarative graph queries: subgraph queries and regular path queries.

Overview

In this chapter, we give a broad overview of the general techniques for processing two classes of graph queries: subgraph queries, which find instances of a query subgraph in a larger input graph, and regular path queries (RPQs), which find pairs of nodes in the graph connected by a path matching a given regular expression. Certainly, software that manage and process graph-structured data, such as RDF triple stores (Neumann and Weikum (2010), Virtuoso), graph database management systems (GDBMSes) (Kankanamge et al. (2017), neo4j),...

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

Access this chapter

Log in via an institution

Institutional subscriptions

Notes

  1. 1.

    The only exception we are aware of is the LogicBlox system (Aref et al. 2015)

  2. 2.

    This can be achieved, for example, by first checking the sizes of the adjacency lists that need to be intersected and starting intersecting the elements in the smallest list in others.

References

  • Aberger CR, Tu S, Olukotun K, Ré C (2016) EmptyHeaded: a relational engine for graph processing. In: SIGMOD

    Google Scholar 

  • Agrawal R (1988) Alpha: an extension of relational algebra to express a class of recursive queries. IEEE TSE 14(7):879–885

    Google Scholar 

  • Aref M, ten Cate B, Green TJ, Kimelfeld B, Olteanu D, Pasalic E, Veldhuizen TL, Washburn G (2015) Design and implementation of the logicblox system. In: SIGMOD

    Google Scholar 

  • Atserias A, Grohe M, Marx D (2013) Size bounds and query plans for relational joins. SIAM J Comput 42(4):1737–1767

    Google Scholar 

  • Consens MP, Mendelzon AO, Vista D, Wood PT (1995) Constant propagation versus join reordering in datalog. In: Rules in database systems. Springer, Berlin, Heidelberg, pp 245–259

    Google Scholar 

  • Cordella L, Foggia P, Sansone C, Vento M (2004) A (sub)graph isomorphism algorithm for matching large graphs. TPAMI 26(10):1367–1372

    Google Scholar 

  • Dey S, Cuevas-Vicenttín V, Köhler S, Gribkoff E, Wang M, Ludäscher B (2013) On implementing provenance-aware regular path queries with relational query engines. In: Proceedings of the joint EDBT/ICDT 2013 workshops. ACM, pp 214–223

    Google Scholar 

  • Färber F, Cha SK, Primsch J, Bornhövd C, Sigg S, Lehner W (2012) SAP HANA database: data management for modern business applications. SIGMOD Rec 40(4): 45–51

    Google Scholar 

  • Fletcher GH, Peters J, Poulovassilis A (2016) Efficient regular path query evaluation using path indexes. In: Proceedings of the 19th international conference on extending database technology

    Google Scholar 

  • Gou G, Chirkova R (2007) Efficiently querying large XML data repositories: a survey. TKDE 19(10): 1381–1403

    Google Scholar 

  • Gubichev A, Bedathur SJ, Seufert S (2013) Sparqling Kleene: fast property paths in RDF-3X. In: Workshop on graph data management experiences and systems. ACM, pp 14–20

    Google Scholar 

  • Han WS, Lee J, Lee JH (2013) Turboiso: towards ultrafast and robust subgraph isomorphism search in large graph databases. In: SIGMOD

    Google Scholar 

  • Kankanamge C, Sahu S, Mhedbhi A, Chen J, Salihoglu S (2017) Graphflow: an active graph database. In: SIGMOD

    Google Scholar 

  • Kochut KJ, Janik M (2007) SPARQLeR: extended SPARQL for semantic association discovery. In: The semantic web: research and applications. Springer, Berlin, pp 145–159

    Google Scholar 

  • Koschmieder A, Leser U (2012) Regular path queries on large graphs. In: Scientific and statistical database management. Springer, Berlin/Heidelberg, pp 177–194

    Google Scholar 

  • Lai L, Qin L, Lin X, Zhang Y, Chang L (2016) Scalable distributed subgraph enumeration. In: VLDB

    Google Scholar 

  • Lai L, Qin L, Lin X, Chang L (2017) Scalable subgraph enumeration in MapReduce: a cost-oriented approach. VLDB J 26(3):421–446

    Google Scholar 

  • Losemann K, Martens W (2012) The complexity of evaluating path expressions in SPARQL. In: Proceedings of the 31st symposium on principles of database systems. ACM, pp 101–112

    Google Scholar 

  • Malewicz G, Austern MH, Bik AJ, Dehnert JC, Horn I, Leiser N, Czajkowski G (2010) Pregel: a system for large-scale graph processing. In: SIGMOD

    Google Scholar 

  • Mendelzon A, Wood P (1995) Finding regular simple paths in graph databases. SIAM J Comput 24(6): 1235–1258

    Google Scholar 

  • Neumann T, Weikum G (2010) The RDF-3X engine for scalable management of RDF data. VLDB 19:91–113

    Google Scholar 

  • Ngo HQ, Porat E, Ré C, Rudra A (2012) Worst-case optimal join algorithms. In: PODS

    Google Scholar 

  • Nguyen D, Aref M, Bravenboer M, Kollias G, Ngo HQ, Ré C, Rudra A (2015) Join processing for graph patterns: an old dog with new tricks. In: GRADES workshop

    Google Scholar 

  • Olteanu D, Schleich M (2016) Factorized databases. SIGMOD Rec 45(2):5–16

    Google Scholar 

  • Pérez J, Arenas M, Gutierrez C (2010) nSPARQL: a navigational language for RDF. Web Semant Sci Serv Agents World Wide Web 8(4):255–270

    Google Scholar 

  • Qiao M, Zhang H, Cheng H (2017) Subgraph matching: on compression and computation. VLDB 11(2):17–188

    Google Scholar 

  • Thompson K (1968) Regular expression search algorithm. Commun ACM 11(6):419–422

    Google Scholar 

  • Veldhuizen TL (2012) Leapfrog Triejoin: a worst-case optimal join algorithm. CoRR abs/1210.0481

    Google Scholar 

  • Yakovets N, Godfrey P, Gryz J (2013) Evaluation of SPARQL property paths via recursive SQL. In: AMW

    Google Scholar 

  • Yakovets N, Godfrey P, Gryz J (2016) Query planning for evaluating SPARQL property paths. In: SIGMOD, San Francisco, pp 1875–1889

    Google Scholar 

  • Zauner H, Linse B, Furche T, Bry F (2010) A RPL through RDF: expressive navigation in RDF graphs. In: Web reasoning and rule systems. Springer, Heidelberg, pp 251–257

    Chapter  Google Scholar 

  • Zhao P, Han J (2010) On graph query optimization in large networks. VLDB 3(1–2):340–351

    Google Scholar 

Download references

Author information

Authors and Affiliations

  1. University of Waterloo, Waterloo, ON, Canada

    S. Salihoglu

  2. Eindhoven University of Technology, Eindhoven, Netherlands

    N. Yakovets

Authors
  1. S. Salihoglu
    View author publications

    You can also search for this author in PubMed Google Scholar

  2. N. Yakovets
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding authors

Correspondence to S. Salihoglu or N. Yakovets .

Editor information

Editors and Affiliations

  1. School of Comp. Sci. and Engineering, University of New South Wales School of Comp. Sci. and Engineering, Eveleigh, New South Wales, Australia

    Sherif Sakr

  2. Sch of Info Techno, Building J12, University of Sydney Sch of Info Techno, Building J12, Sydney, Australia

    Albert Zomaya

Section Editor information

  1. Dresden Database Systems Group, Technische Universität Dresden, 01062, Dresden, Germany

    Hannes Voigt

  2. Department of Mathematics and Computer Science, Eindhoven University of Technology http://www.win.tue.nl/~gfletche/

    George Fletcher

Rights and permissions

Reprints and permissions

Copyright information

© 2018 Springer International Publishing AG

About this entry

Check for updates. Verify currency and authenticity via CrossMark

Cite this entry

Salihoglu, S., Yakovets, N. (2018). Graph Query Processing. In: Sakr, S., Zomaya, A. (eds) Encyclopedia of Big Data Technologies. Springer, Cham. https://doi.org/10.1007/978-3-319-63962-8_215-1

Download citation

  • DOI: https://doi.org/10.1007/978-3-319-63962-8_215-1

  • Published:

  • Publisher Name: Springer, Cham

  • Print ISBN: 978-3-319-63962-8

  • Online ISBN: 978-3-319-63962-8

  • eBook Packages: Living Reference MathematicsReference Module Computer Science and Engineering

Publish with us

Policies and ethics