Dean De Leo
ABSTRACT
Reachability and shortest paths are among two of the most common queries realized on graphs. While graph frameworks and property graph databases provide an extensive and convenient built-in support for these operations, it is still both clunky and inefficient to perform on standard SQL DBMSs. In this paper, we present an extension to the standard SQL language to compute both reachability predicates and many-to-many shortest path queries. We first describe a methodology to represent a directed graph starting from virtual table expressions. Second, we introduce a new type of operator to compute shortest paths on the given graph. Our semantic abides by the rules of operating with table expressions, ensuring that the property of the closure from the relational algebra is retained. Finally, we developed a prototype implementation of our extension on top of MonetDB, an existing open source relational DBMS. Our preliminary results still show that dynamically building our representation of the underlying graph overly dominates the query time. Currently, this cost can only be amortized when executing multiple shortest paths on the same graph.
- 2017. AgensGraph. (2017). http://bitnine.net/agensgraph/Google Scholar
- 2017. The Gremlin Graph Traversal Machine and Language. (2017). http://tinkerpop.apache.org/gremlin.htmlGoogle Scholar
- 2017. Hive documentation: Lateral views. (2017). Retrieved March 2017 from https://cwiki.apache.org/confluence/display/Hive/LanguageManual+LateralViewGoogle Scholar
- 2017. Introduction to Apache Giraph. (2017). http://giraph.apache.org/intro.htmlGoogle Scholar
- 2017. LDBC-SNB Data Generator (DATAGEN. (2017). Retrieved March 2017 from https://github.com/ldbc/ldbc_snb_datagenGoogle Scholar
- 2017. LDBC Social Network Benchmark (SNB) specification. (2017). Retrieved March 2017 from https://github.com/ldbc/ldbc_snb_docsGoogle Scholar
- 2017. The openCypher project. (2017). http://www.opencypher.org/Google Scholar
- 2017. OpenLink Virtuoso documentation. Transitivity in SQL. (2017). http://docs.openlinksw.com/virtuoso/transitivityinsql/Google Scholar
- 2017. SAP Hana Graph documentation. (2017). help.sap.com/hana/SAP_HANA_Graph_Reference_en.pdfGoogle Scholar
- 2017. Snowflake documentation: FLATTEN table function. (2017). Retrieved March 2017 from https://docs.snowflake.net/manuals/sql-reference/functions/flatten.htmlGoogle Scholar
- Ravindra K. Ahuja, Kurt Mehlhorn, James Orlin, and Robert E. Tarjan. 1993. Faster algorithms for the shortest path problem. Journal of the ACM (JACM) 37, 2 (April 1993), 212--223. Google ScholarDigital Library
- C.J. Date. 2011. SQL and Relational Theory: How to Write Accurate SQL Code (2nd ed.). O'Really. Google ScholarDigital Library
- Orri Erling, Alex Averbuch, Josep Larriba-Pey, Hassan Chafi, Andrey Gubichev, Arnau Prat, Minh-Duc Pham, and Peter Boncz. 2015. The LDBC Social Network Benchmark: Interactive Workload. In Proceedings of the 2015 ACM SIGMOD International Conference on Management of Data. 619--630. Google ScholarDigital Library
- Jing Fan, Adalbert Gerald Soosai Raj, and Jignesh M. Patel. 2015. The Case Against Specialized Graph Analytics Engines. In CIDR.Google Scholar
- ISO. 2011. ISO/IEC 9075-2:2011 Information technology - Database languages - SQL - Part 2: Foundation (SQL/Foundation). International Organization for Standardization. https://www.iso.org/standard/53682.htmlGoogle Scholar
- MonetDB team. 2017. MonetDB. (2017). Retrieved March 2017 from https://www.monetdb.org/Google Scholar
- Adam Welc, Raghavan Raman, Zhe Wu, Sungpack Hong, Hassan Chafi, and Jay Banerjee. 2013. Graph Analysis: Do We Have to Reinvent the Wheel?. In First International Workshop on Graph Data Management Experiences and Systems (GRADES '13). ACM, New York, NY, USA, Article 7, 6 pages. Google ScholarDigital Library
- Extending SQL for Computing Shortest Paths
Recommendations
Computing shortest paths with uncertainty
We consider the problem of estimating the length of the shortest path from a vertex s to a vertex t in a DAG whose edge lengths are known only approximately but can be determined exactly at a cost. Initially, for each edge e, the length of e is known ...
Shortest paths in Sierpiński graphs
In 23], Klav ar and Milutinović (1997) proved that there exist at most two different shortest paths between any two vertices in Sierpiński graphs S k n , and showed that the number of shortest paths between any fixed pair of vertices of S k n can be ...
On shortest disjoint paths in planar graphs
For a graph G and a collection of vertex pairs {(s"1,t"1),...,(s"k,t"k)}, the k disjoint paths problem is to find k vertex-disjoint paths P"1,...,P"k, where P"i is a path from s"i to t"i for each i=1,...,k. In the corresponding optimization problem, the ...
Comments