IPSJ SIG Technical Report Vol.2015-HPC-150 No /8/5 Property Path SPARQL 1,a) 1,b) RDB RDF SPARQL RDF SPARQL SPARQL SPARQL1.1 Property Path SPAR

Size: px

Start display at page:

Download "IPSJ SIG Technical Report Vol.2015-HPC-150 No /8/5 Property Path SPARQL 1,a) 1,b) RDB RDF SPARQL RDF SPARQL SPARQL SPARQL1.1 Property Path SPAR"

ひでかさわい
5 years ago
Views:

1 Property Path SPARQL 1,a) 1,b) RDB RDF SPARQL RDF SPARQL SPARQL SPARQL1.1 Property Path SPARQL Property Path Property Path SPARQL SPARQL Property Path RDF SPARQL Property Path A SPARQL Processing System Supporting Efficient Property Path Search Ishikawa Yasutaka 1,a) Kenjiro Taura 1,b) Abstract: In many area, for example, semantic web, social network, we can see the data including graph structure, and more efficient system for graph data is needed with increasing of the amount of data. Up to date, several new graph specific systems have been proposed because existing system like Relational DataBase RDB is not suitable for graph traversal. SPARQL processing system is one of these graph specific systems which managing RDF graph data and SPARQL query, one of graph query languages. Besides, the latest SPARQL specification, SPARQL1.1, has Property Path query which enable us to write query with using regular expression and enhance the power of expression. However, many SPARQL processing system can t manage Property Path query, and systems following SPARQL1.1 don t provide enough searching power. Therefore, in this article, I propose new SPARQL processing system, which can manage Property Path query and provide enough searching power by using several techniques and efficient parallelization. Keywords: Graph Processing System, RDF SPARQL Property Path 1. 1 University of Tokyo a) ishikawa@eidos.ic.i.u-tokyo.ac.jp b) tau@eidos.ic.i.u-tokyo.ac.jp IoT Internet of Things 1

2 IDC [1] ZB ZB Facebook Twitter SNS vertex edge facebook twitter SNS [2] RDB RDB join GraphDB GraphDB graph processing system graph database neo4j[3], HypergraphDB[4] Pregel[5], Trinity[6] GraphDB [7] Regular Path Query RPQ edge vertex *? RDF[8] SPARQL[9][10] RDF subject object predicate 3 triple SPARQL RDF RDB SQL SPARQL SPARQL1.0 [11][12] SPARQL1.0 RPQ SPARQL1.0 W3C[13] SPARQL1.1[10] Property Path RPQ [14] SPARQL1.1 Property Path SPARQL 2 3 SPARQL 4 SPARQL vertex edge label vertex edge property graph[15] edge vertex vertex Facebook twitter SNS 2.2 Regular Path Query Regular Path Query RPQ [7] RPQ 2

subject object vertex predicate subject object edge RDF triple xml RDF/XML[16] 3 Tony Benn http://en.wikipedia.

3 property graph 1 RPQ a b vertex 2.3 RDF a b a a b 1 Regular Path Query RDF[8] 2 RDF subject object RDF DBpedia[17] web web RDF WWW HTML WWW DBpedia RDF web 2.4 SPARQL SPARQL SQL RDF SPARQL 4 Grap h RDF A d a c B Subjec t P redicate Objec t A a B A d C D b C B c C C d D 4 SPARQL 2 Each tuple is triple RDF predicate 3 triple subject object vertex predicate subject object edge RDF triple xml RDF/XML[16] 3 Tony Benn wiki/tonybenn dc:title dc:publishe r Wikipedi a 4 SPARQL 2.5 SPARQL 2008 W3C W3C Property Path SPARQL1.0 RPQ SPARQL1.1 Property Path RPQ 5 SPARQL1.1 Property Path vertex like vertex 3 Notation SPARQL Hammoud [12] SPARQL 4 ( 1 ) 3

4 1 SPARQL Processing System Parallelism Managing Proerty Path RDF-3X[18] parallelized as category1 No TripleBit[19] parallelized as category1 No Hexastore[20] parallelized as category1 No Sesame[21] not sufficient Yes Jena[22] not sufficient Yes Trinity.RDF[11] distributed as category2 No DREAM[12] distributed as category3 No Property Path 2 5 Property Path Query ( 2 ) ( 3 ) ( 4 ) 1 RDF-3X[18] TripleBit[19] Hexastore[20] RDF SPARQL1.1 Property Path Property Path Sesame[21] Jena[22] Property Path 3.2 SPARQL1.1 [14] vertex Trinity.RDF[11] DREAM[12] Huang [23] DREAM 4 Master-Slave Master Slave Slave 1 Master Property Path Huang 2 Property Path 3.2 SPARQL W3C SPARQL1.0[9] 2013 W3C SPARQL1.1[10] Property Path [14] vertex [14] SPARQL1.1 SPARQL 13 vertex vertex edge1 Property Path 4. SPARQL1.1 Property Path Property Path SPARQL1.1 5 vertex 4

5 vertex a b c 5 A,B Bob, Alice Bob Alice e d Property Path Property Path query predicate elt : elt 0 elt+: elt 1 elt?: elt 0 1 elt1/elt2: elt1 elt2 êlt: elt elt1 elt2: elt1 elt2 elt{n, m}: elt n m A a a B C e b c F D E d 4.2 RPQ Regular Path Query RPQ vertex SPARQL Property Path [24] RPQ Algrithm.1 Algorithm 1 Parallelized property path query Input: graph G, property path query Q, Memotable M(= ϕ), queue q(= ϕ) Output: a set of node pairs N 1: divide edges of G by label 2: convert Q into NFA A L 3: for a node n 0 in G do 4: add the pair{n 0, start state S 0 in A L } to q and M 5: while q is not empty(in parallel) do 6: pop pair {n, S} from q 7: if S is final state F then 8: add the pair{n, n 0 } to N 9: continue 10: for label l outgoing from S do 11: for node n next linked with n by label l in G do 12: if pair {n next, S next } is not in M then 13: add {n next, S next } to q,m 14: clear M graph 6 Property Path Query NFA SPARQL NFA vertex NFA NFA vertex vertex vertex 6 B,C q 1 D 4.3 Property Path vertex centrality centrality centrality betweeness centrality degree centrality closeness centrality betweeness centrality 2 vertex 5

6 degree centrality vertex edge centrality vertex central vertex RDF web-graph vertex vertex vertex vertex centrality web web web Property Path 2 central vertex central vertex Property Path 8 St ar t ve rtex Central Central Central End vertex A E G central vertex 4.4 Property Path SPARQL 9 9 Triple SPARQL These result are useles s?a?b Alice Dave Eve Bob Matild a Charlie Ellen Bob Flank Carol?A soccer Eve - "?B Running Bob - 7 Property Path 10 Triple central vertex 7 8 vertex central vertex vertex central vertex 8 Property Path vertex central vertex 10 Property Path Property Path join [12] 6

7 情報処理学会研究報告本システムでは同一ノード内において Property Path のようになっているを含んだようなクエリの並べ替えによるクエリ実行の高速化を提案する提案する並べ替えのセマンティクスは次の通りである ( 1 ) 辿る edge が多いものはより後に実行されるまた * を含んだクエリは一番後に実行される ( 2 ) サブクエリの vertex が変数ではなくリテラルであった場合そのサブクエリは先に実行される ( 3 ) サブクエリに含まれたラベルのグラフにおける出現回数が多い場合そのサブクエリはより後に実行さ図 12 Q1 図 13 Q2 図 14 Q3 れるこれらを図 9 のクエリに適用すると図 11 のようになるこの順序でクエリを直列に実行することによって?A?B に対する検索の候補を最初から絞ることが出来 Property Path クエリ探索を実行する際の探索の開始点を大きく絞って計算を大幅に枝刈りすることが可能になる " " " Q1 を例に取るとこれは取っている授業を辿っていった両端の学生の出身校が指定の場所であった場合二人の名前を返すようなクエリであるこの Q1 を並べ替えると図 15 のようになる図 11 Property Path を含むクエリの並べ替え 5. 実験現在実装途中であるため今回は予備実験として 4.4 節で述べたクエリの実行順序並べ替えによる効果の測定を行ったなおクエリの並べ替えは手動で行っておりここでは並列化は行っていない実験にはデータセット生成のために LUBM[25] を使図 15 実行順序変更後の Q1 用したこれによって学術情報に関するオントロジーを表す人工データを生成することが出来データサイズは任意 Q1 3 に対して手動で並び替えを行いそれぞれをデーに指定出来る実験環境としては Intel R Xeon R タセットに対して実行して比較したのが次の図 16 であ CPU E v3 2.30GHz メモリは 770GB のマシンるなお縦軸は対数スケールとなっているを用い C++を用いて実装を行った示されているようにいずれも並び替え後の実行時間測定には 3 つの全て Property Path を含んだようなクは短くなっている Q2 の場合は性能の向上幅はさほど大エリを使用しそれぞれ Q1 Q2 Q3 とするこれらは図きくないが Q1 Q3 の実行の際には検索速度が大幅に 2015 Information Processing Society of Japan 7

8 time[ms] Not ordered Orderd Q1 Q2 Q3 Query 16 Q1 Q3 SPARQL Vertex Property Path Q2 Vertex Property Path Property Path 6. Regular Path Query RDF SPARQL SPARQL RPQ Property Path Property Path RPQ Property Path web-scale [1] : The Digital Universe of Opportunities: Rich Data and the IncreasingValue of the Internet of Things, digital-universe/2014iview/index.htm (2014). [2] Ugander, J., Karrer, B., Backstrom, L. and Marlow, C.: The Anatomy of the Facebook Social Graph, p. 17 (online), available from (2011). [3] : neo4j - The World s Leading Graph Database, http: // (2012). [4] Iordanov, B.: HyperGraphDB: A Generalized Graph Database, Web-Age Information Management, Vol (online), available from (2010). [5] Malewicz, G., Austern, M. H., Bik, A. J. C., Dehnert, J. C., Horn, I., Leiser, N. and Czajkowski, G.: Pregel, Proceedings of the 2010 international conference on Management of data - SIGMOD 10, New York, New York, USA, ACM Press, p. 135 (online), DOI: / (2010). [6] Shao, B., Wang, H. and Li, Y.: Trinity, Proceedings of the 2013 international conference on Management of data - SIGMOD 13, New York, New York, USA, ACM Press, p. 505 (online), DOI: / (2013). [7] Barceló Baeza, P.: Querying graph databases, Proceedings of the 32nd symposium on Principles of database systems - PODS 13, p. 175 (online), DOI: / (2013). [8] : RDF 1.1 Concepts and Abstract Syntax, w3.org/tr/rdf11-concepts/ (2014). [9] : SPARQL Query Language for RDF, org/tr/rdf-sparql-query/ (2008). [10] : SPARQL 1.1 Query Language, TR/sparql11-query/ (2013). [11] Zeng, K., Yang, J., Wang, H., Shao, B. and Wang, Z.: A distributed graph engine for web scale RDF data, Proceedings of the VLDB Endowment, Vol. 6, No. 4, pp (online), DOI: / (2013). [12] Hammoud, M., Rabbou, D. A. and Nouri, R.: DREAM : Distributed RDF Engine with Adaptive Query Planner and Minimal Communication, Proceedings of the VLDB Endowment, Vol. 8, No. 6, pp (2015). [13] : World Wide Web Consortium (W3C), WorldWideWebConsortium(W3C). [14] Arenas, M., Conca, S. and Pérez, J.: Counting beyond a Yottabyte, or how SPARQL 1.1 property paths will prevent adoption of the standard, Proceedings of the 21st international conference on World Wide Web - WWW 12, p. 629 (online), DOI: / (2012). [15] Rodriguez, M. a. and Neubauer, P.: Constructions from Dots and Lines, Vol. X, No. X, pp (online), DOI: /bult (2010). [16] : RDF 1.1 XML Syntax, rdf-syntax-grammar/ (2014). [17] Auer, S., Bizer, C., Kobilarov, G., Lehmann, J., Cyganiak, R. and Ives, Z.: DBpedia: A nucleus for a Web of open data, Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), Vol

9 LNCS, pp (online), DOI: / (2007). [18] Neumann, T. and Weikum, G.: The RDF-3X engine for scalable management of RDF data, VLDB Journal, Vol. 19, No. 1, pp (online), DOI: /s y (2010). [19] Yuan, P., Liu, P., Wu, B., Jin, H., Zhang, W. and Liu, L.: TripleBit: A Fast and Compact System for Large Scale RDF Data, Proc. VLDB Endow., Vol. 6, No. 7, pp (online), DOI: / (2013). [20] Weiss, C. U. O. Z., Weiss, C., Karras, P. N. U. o. S., Bernstein, A. U. o. Z., Karras, P. and Bernstein, A.: Hexastore: sextuple indexing for semantic web data management, Proceedings of the VLDB Endowment archive, Vol. 1, No. 1, pp (online), DOI: / (2008). [21] Broekstra, J., Kampman, A. and Harmelen, F. V.: Sesame: A Generic Architecture for Storing and Querying RDF and RDF Schema, International Semantic Web Conference ISWC, Vol. 1, pp (online), DOI: / (2002). [22] Wilkinson, K., Sayers, C., Kuno, H. and Reynolds, D.: Efficient RDF storage and retrieval in Jena2, Proceedings 1th International Workshop on Semantic Web and Databases, pp (online), DOI: citeulike-articleid: (2003). [23] Huang, J., Abadi, D. J. and Ren, K.: Scalable SPARQL Querying of Large RDF Graphs, Proceedings of the VLDB Endowment, Vol. 4, No. 11, pp (online), available from (2011). [24] Iwanari, T.: Graph Database Regular Path Query (2015). [25] : The LUBM Benchmark, edu/projects/lubm/. 9

Vol.55 No (Jan. 2014) saccess 6 saccess 7 saccess 2. [3] p.33 * B (A) (B) (C) (D) (E) (F) *1 [3], [4] Web PDF a m

Vol.55 No (Jan. 2014) saccess 6 saccess 7 saccess 2. [3] p.33 * B (A) (B) (C) (D) (E) (F) *1 [3], [4] Web PDF a m Vol.55 No.1 2 15 (Jan. 2014) 1,a) 2,3,b) 4,3,c) 3,d) 2013 3 18, 2013 10 9 saccess 1 1 saccess saccess Design and Implementation of an Online Tool for Database Education Hiroyuki Nagataki 1,a) Yoshiaki