Sage Journals: Discover world-class research

Abstract

Traditional approaches for querying the Web of Data often involve centralised warehouses that replicate remote data. Conversely, Linked Data principles allow for answering queries live over the Web by dereferencing URIs to traverse remote data sources at runtime. A number of authors have looked at answering SPARQL queries in such a manner; these link-traversal based query execution (LTBQE) approaches for Linked Data offer up-to-date results and decentralised (i.e., client-side) execution, but must operate over incomplete dereferenceable knowledge available in remote documents, thus affecting response times and “recall” for query answers. In this paper, we study the recall and effectiveness of LTBQE, in practice, for the Web of Data. Furthermore, to integrate data from diverse sources, we propose lightweight reasoning extensions to help find additional answers. From the state-of-the-art which (1) considers only dereferenceable information and (2) follows rdfs:seeAlso links, we propose extensions to consider (3) owl:sameAs links and reasoning, and (4) lightweight RDFS reasoning. We then estimate the recall of link-traversal query techniques in practice: we analyse a large crawl of the Web of Data (the BTC’11 dataset), looking at the ratio of raw data contained in dereferenceable documents vs. the corpus as a whole and determining how much more raw data our extensions make available for query answering. We then stress-test LTBQE (and our extensions) in real-world settings using the FedBench and DBpedia SPARQL Benchmark frameworks, and propose a novel benchmark called QWalk based on random walks through diverse data. We show that link-traversal query approaches often work well in uncontrolled environments for simple queries, but need to retrieve an unfeasible number of sources for more complex queries. We also show that our reasoning extensions increase recall at the cost of slower execution, often increasing the rate at which results return; conversely, we show that reasoning aggravates performance issues for complex queries.

Keywords

Linked data SPARQL RDFS OWL Semantic Web RDF Web of Data live querying reasoning

Get full access to this article

View all access options for this article.

References

[1]

Acosta,

Vidal,

Lampo,

Castillo and

Ruckhaus, ANAPSID: An adaptive query processing engine for SPARQL endpoints, in: Aroyo et al. [8], pp. 18–34.

[2]

Alkhateeb,

Baget and

Euzenat, Extending SPARQL with regular expression patterns (for querying RDF), J. Web Sem. 7(2) (2009), 57–73.

[3]

Antoniou,

Grobelnik,

E.P.B.

Simperl,

Parsia,

Plexousakis,

P.D.

Leenheer and

J.Z.

Pan, eds, The Semantic Web: Research and Applications, Proc. of the 8th Extended Semantic Web Conference, ESWC 2011, Part I, Heraklion, Crete, Greece, May 29–June 2, 2011, Lecture Notes in Computer Science, Vol. 6643, Springer, 2011.

[4]

C.B.

Aranda,

Arenas and

Ó.

Corcho, Semantics and optimization of the SPARQL 1.1 federation extension, in: The Semanic Web: Research and Applications, Proc. of the 8th Extended Semantic Web Conference, ESWC 2011, Part II, Heraklion, Crete, Greece, May 29–June 2, 2011,

Antoniou,

Grobelnik,

E.P.B.

Simperl,

Parsia,

Plexousakis,

P.D.

Leenheer and

J.Z.

Pan, eds, Lecture Notes in Computer Science, Vol. 6644, Springer, 2011, pp. 1–15.

[5]

C.B.

Aranda,

Hogan,

Umbrich and

Vandenbussche, SPARQL web-querying infrastructure: Ready for action? in: The Semantic Web – ISWC 2013, Proc. of the, 12th International Semantic Web Conference, Part II, Sydney, NSW, Australia, October 21–25, 2013,

Alani,

Kagal,

Fokoue,

P.T.

Groth,

Biemann,

J.X.

Parreira,

Aroyo,

N.F.

Noy,

Welty and

Janowicz, eds, Lecture Notes in Computer Science, Vol. 8219, Springer, 2013, pp. 277–293.

[6]

Arenas,

Gutierrez,

D.P.

Miranker,

Pérez and

Sequeda, Querying semantic data on the web? SIGMOD Record 41(4) (2012), 6–17.

[7]

Arias,

J.D.

Fernández,

M.A.

Martínez-Prieto and

de la Fuente, An empirical study of real-world SPARQL queries, CoRR abs/1103.5043 (2011).

[8]

Aroyo,

Welty,

Alani,

Taylor,

Bernstein,

Kagal,

N.F.

Noy and

Blomqvist, eds, The Semantic Web – ISWC 2011, Proc. of the 10th International Semantic Web Conference, Part I, Bonn, Germany, October 23–27, 2011, Lecture Notes in Computer Science, Vol. 7031, Springer, 2011.

[9]

Bechhofer,

Hauswirth,

Hoffmann and

Koubarakis, eds, The Semantic Web: Research and Applications, Proc. of the 5th European Semantic Web Conference, ESWC 2008, Tenerife, Canary Islands, Spain, June 1–5, 2008, Lecture Notes in Computer Science, Vol. 5021, Springer, 2008.

10.

[10]

Berners-Lee, Linked Data, Design issues, 2006, W3C.

11.

[11]

Bernstein,

D.R.

Karger,

Heath,

Feigenbaum,

Maynard,

Motta and

Thirunarayan, eds, The Semantic Web – ISWC 2009, Proc. of the 8th International Semantic Web Conference, ISWC 2009, Chantilly, VA, USA, October 25–29, 2009, Lecture Notes in Computer Science, Vol. 5823, Springer, 2009, pp. 25–29.

12.

[12]

Bishop,

Kiryakov,

Ognyanoff,

Peikov,

Tashev and

Velkov, OWLIM: A family of scalable semantic repositories, Semantic Web 2(1) (2011), 33–42.

13.

[13]

Bishop,

Kiryakov,

Ognyanov,

Peikov,

Tashev and

Velkov, Factforge: A fast track to the web of data, Semantic Web 2(2) (2011), 157–166.

14.

[14]

Bizer,

Heath,

Berners-Lee and

Hausenblas, eds, WWW2011 Workshop on Linked Data on the Web, Hyderabad, India, March 29, 2011, CEUR Workshop Proceedings, Vol. 813, CEUR-WS.org, 2011.

15.

[15]

Bizer and

Schultz, The Berlin SPARQL Benchmark, International Journal on Semantic Web and Information Systems 5(2) (2009), 1–24.

16.

[16]

P.A.

Bonatti,

Hogan,

Polleres and

Sauro, Robust and scalable linked data reasoning incorporating provenance and trust annotations, J. Web Sem. 9(2) (2011), 165–201.

17.

[17]

Bouquet,

Ghidini and

Serafini, A formal model of queries on interlinked RDF graphs, in: Linked Data Meets Artificial Intelligence, Papers from the 2010 AAAI Spring Symposium, Stanford, California, USA, March 22–24, 2010, AAAI, 2010, pp. 22–24, Technical Report SS-10-07.

18.

[18]

Cheng and

Qu, Term dependence on the Semantic Web, in: International Semantic Web Conference, 2008, pp. 665–680.

19.

[19]

Cyganiak,

Hogan and

Harth, N-Quads: Extending N-Triples with context, http://sw.deri.org/2008/07/n-quads/.

20.

[20]

Delbru,

Tummarello and

Polleres, Context-dependent OWL reasoning in sindice – Experiences and lessons learnt, in: Web Reasoning and Rule Systems, Proc. of the 5th International Conference RR 2011, Galway, Ireland, August 29–30, 2011,

Rudolph and

Gutierrez, eds, Lecture Notes in Computer Science, Vol. 6902, Springer, 2011, pp. 46–60.

21.

[21]

Ding,

Shinavier,

Shangguan and

D.L.

McGuinness, Sameas networks and beyond: Analyzing deployment status and implications of owl: Sameas in linked data, in: Patel-Schneider et al. [51], pp. 145–160.

22.

[22]

Erling and

Mikhailov, RDF support in the virtuoso DBMS, in: The Social Semantic Web 2007, Proc. of the 1st Conference on Social Semantic Web (CSSW), Leipzig, Germany, September 26–28, 2007,

Auer,

Bizer,

Müller and

A.V.

Zhdanova, eds, LNI, Vol. 113, GI, 2007, pp. 59– 68.

23.

[23]

Fionda,

Gutierrez and

Pirrò, Semantic navigation on the web of data: Specification of routes, web fragments and actions, in: Proc. of the 21st World Wide Web Conference 2012, WWW 2012, Lyon, France, April 16–20, 2012,

Mille,

F.L.

Gandon,

Misselis,

Rabinovich and

Staab, eds, ACM, 2012 pp. 281–290.

24.

[24]

Glimm,

Hogan,

Krötzsch and

Polleres, OWL: yet to arrive on the web of data? in: WWW2012 Workshop on Linked Data on the Web, Lyon, France, 16 April, 2012,

Bizer,

Heath,

Berners-Lee and

Hausenblas, eds, CEUR Workshop Proceedings, Vol. 937, CEUR-WS.org, 2012.

25.

[25]

Görlitz and

Staab, SPLENDID: SPARQL endpoint federation exploiting VOID descriptions, in: Proc. of the Second International Workshop on Consuming Linked Data (COLD2011), Bonn, Germany, October 23, 2011,

Hartig,

Harth and

Sequeda, eds, CEUR Workshop Proceedings, Vol. 782, CEUR-WS.org, 2011.

26.

[26]

Guo,

Pan and

Heflin, LUBM: A benchmark for OWL knowledge base systems, J. Web Sem. 3(2–3) (2005), 158– 182.

27.

[27]

Halpin,

P.J.

Hayes,

J.P.

McCusker,

D.L.

McGuinness and

H.S.

Thompson, When owl:sameAs isn’t the same: An analysis of identity in Linked Data, in: International Semantic Web Conference, 2010.

28.

[28]

Harris and

Seaborne, SPARQL 1.1 query language, W3C Recommendation, 2013.

29.

[29]

Harth and

Speiser, On completeness classes for query evaluation on linked data, in: Proc. of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22–26, 2012,

Hoffmann and

Selman, eds, AAAI Press, 2012.

30.

[30]

Harth,

Umbrich,

Hogan and

Decker, YARS2: A federated repository for querying graph structured data from the Web, in: International Semantic Web Conference, 2007.

31.

[31]

Hartig, How caching improves efficiency and result completeness for querying linked data, in: Bizer et al. [14].

32.

[32]

Hartig, Zero-knowledge query planning for an iterator implementation of link traversal based query execution, in: Antoniou et al. [3], pp. 154–169.

33.

[33]

Hartig, SPARQL for a web of linked data: Semantics and computability, in: The Semantic Web: Research and Applications, Proc. of the 9th Extended Semantic Web Conference, ESWC 2012, Heraklion, Crete, Greece, May 27–31, 2012,

Simperl,

Cimiano,

Polleres,

Ó.

Corcho and

Presutti, eds, Lecture Notes in Computer Science, Vol. 7295, Springer, 2012, pp. 8–23.

34.

[34]

Hartig,

Bizer and

J.C.

Freytag, Executing SPARQL queries over the web of linked data, in: Bernstein et al. [11], pp. 293–309.

35.

[35]

Hartig and

Freytag, Foundations of traversal based query execution over linked data, in: 23rd ACM Conference on Hypertext and Social Media, HT ’12, Milwaukee, WI, USA, June 25–28, 2012,

E.V.

Munson and

Strohmaier, eds, ACM, 2012, pp. 43–52.

36.

[36]

Hartig and

Huber, A main memory index structure to query linked data, in: Bizer et al. [14].

37.

[37]

Hartig and

Langegger, A database perspective on consuming Linked Data on the Web. Datenbank-Spektrum, 2010.

38.

[38]P. Hayes, RDF semantics, W3C Recommendation, Feb. 2004.

39.

[39]

Heath and

Bizer, Linked Data: Evolving the Web Into a Global Data Space, Synthesis Lectures on the Semantic Web, Morgan & Claypool Publishers, 2011.

40.

[40]

Hogan,

Harth and

Polleres, Scalable authoritative Owl reasoning for the Web, International Journal Semantic Web Information Systems 5(2) (2009), 49–90.

41.

[41]

Hogan,

Zimmermann,

Umbrich,

Polleres and

Decker, Scalable and distributed methods for entity matching, consolidation and disambiguation over linked data corpora, J. Web Sem. 10 (2012), 76–110.

42.

[42]

Hose,

Schenkel,

Theobald and

Weikum, Database foundations for scalable RDF processing, in: Reasoning Web. Semantic Technologies for the Web of Data, Tutorial Lectures of 7th International Summer School 2011, Galway, Ireland, August 23–27, 2011,

Polleres,

d’Amato,

Arenas,

Handschuh,

Kroner,

Ossowski and

P.F.

Patel-Schneider, eds, Lecture Notes in Computer Science, Vol. 6848, Springer, 2011, pp. 202–249.

43.

[43]

Käfer,

Abdelrahman,

Umbrich,

O’Byrne and

Hogan, Observing linked data dynamics, in: The Semantic Web: Semantics and Big Data, Proc. of the 10th International Conference, ESWC 2013, Montpellier, France, May 26–30, 2013,

Cimiano,

Ó.

Corcho,

Presutti,

Hollink and

Rudolph, eds, Lecture Notes in Computer Science, Vol. 7882, Springer, 2013, pp. 213–227.

44.

[44]

Ladwig and

Tran, Linked data query processing strategies, in: Patel-Schneider et al. [51], pp. 453–469.

45.

[45]

Ladwig and

Tran, Sihjoin: Querying remote and local linked data, in: Antoniou et al. [3], pp. 139–153.

46.

[46]

Langegger,

Wöß and

Blöchl, A semantic web middleware for virtual data integration on the web, in: Bechhofer et al. [9], pp. 493–507.

47.

[47]

Li and

Heflin, Using reformulation trees to optimize queries over distributed heterogeneous sources, in: Patel-Schneider et al. [51], pp. 502–517.

48.

[48]

Morsey,

Lehmann,

Auer and

A.N.

Ngomo, Dbpedia SPARQL benchmark – Performance assessment with real queries on real data, in: Aroyo et al. [8], pp. 454–469.

49.

[49]

Muñoz,

Pérez and

Gutierrez, Simple and efficient minimal RDFS, J. Web Sem. 7(3) (2009), 220–234.

50.

[50]

Oren,

Delbru,

Catasta,

Cyganiak,

Stenzhorn and

Tummarello, Sindice.com: A document-oriented lookup index for open linked data, IJMSO 3(1) (2008), 37–52.

51.

[51]

P.F.

Patel-Schneider,

Pan,

Hitzler,

Mika,

Zhang,

J.Z.

Pan,

Horrocks and

Glimm, eds, The Semantic Web – 9th International Semantic Web Conference, ISWC 2010, Revised Selected Papers, Part I, Shanghai, China, November 7–11, 2010, Lecture Notes in Computer Science, Vol. 6496, Springer, 2010.

52.

[52]

Pérez,

Arenas and

Gutierrez, Semantics and complexity of SPARQL, in: International Semantic Web Conference, 2006, pp. 30–43.

53.

[53]

Pérez,

Arenas and

Gutierrez, nsparql: A navigational language for RDF, J. Web Sem. 8(4) (2010), 255–270.

54.

[54]

Prud’hommeaux and

Seaborne, SPARQL query language for RDF, W3C Recommendation, Jan. 2008.

55.

[55]

Quilitz and

Leser, Querying distributed RDF data sources with SPARQL, in: Bechhofer et al. [9], pp. 524–538.

56.

[56]

Schmidt,

Görlitz,

Haase,

Ladwig,

Schwarte and

Tran, Fedbench: A benchmark suite for federated semantic data query processing, in: Aroyo et al. [8], pp. 585–600.

57.

[57]

Schmidt,

Hornung,

Küchlin,

Lausen and

Pinkel, An experimental comparison of RDF data management approaches in a SPARQL benchmark scenario, in: The Semantic Web, Proc. of the 7th International Semantic Web Conference, ISWC 2008, Karlsruhe, Germany, October 26–30, 2008,

A.P.

Sheth,

Staab,

Dean,

Paolucci,

Maynard,

T.W.

Finin and

Thirunarayan, eds, Lecture Notes in Computer Science, Vol. 5318, Springer, 2008, pp. 82–97.

58.

[58]

Schmidt,

Hornung,

Meier,

Pinkel and

Lausen, Sp²bench: A SPARQL performance benchmark, in: Semantic Web Information Management – A Model-Based Perspective,

R.D.

Virgilio,

Giunchiglia and

Tanca, eds, Springer, 2009, pp. 371–393.

59.

[59]

Schwarte,

Haase,

Hose,

Schenkel and

Schmidt, Fedx: Optimization techniques for federated query processing on linked data, in: Aroyo et al. [8], pp. 601–616.

60.

[60]

Stuckenschmidt,

Vdovjak,

Houben and

Broekstra, Index structures and algorithms for querying distributed RDF repositories, in: Proc. of the 13th International Conference on World Wide Web, WWW 2004, New York, NY, USA, May 17–20, 2004,

S.I.

Feldman,

Uretsky,

Najork and

C.E.

Wills, eds, ACM, 2004, pp. 631–639.

61.

[61]

Tran,

Zhang and

Studer, Summary models for routing keywords to linked data sources, in: Patel-Schneider et al. [51], pp. 781–797.

62.

[62]

Umbrich, A hybrid framework for querying Linked Data dynamically, PhD Thesis, NUI Galway, 2012, http://aran. library.nuigalway.ie/xmlui/handle/10379/3360.

63.

[63]

Umbrich,

Gutierrez,

Hogan,

Karnstedt and

J.X.

Parreira, The ACE theorem for querying the web of data, in: 22nd International World Wide Web Conference, WWW ’13, Companion Volume, Rio de Janeiro, Brazil, May 13–17, 2013,

Carr,

A.H.F.

Laender,

B.F.

Lóscio,

King,

Fontoura,

Vrandecic

Aroyo,

J.P.M.

de Oliveira,

Lima and

Wilde, eds, ACM, 2013, pp. 133–134, International World Wide Web Conferences Steering Committee.

64.

[64]

Umbrich,

Hogan,

Polleres and

Decker, Improving the recall of live linked data querying through reasoning, in: Web Reasoning and Rule Systems, Proc. of the 6th International Conference, RR 2012, Vienna, Austria, September 10–12, 2012,

Krötzsch and

Straccia, eds, Lecture Notes in Computer Science, Vol. 7497, Springer, 2012, pp. 188–204.

65.

[65]

Umbrich,

Hose,

Karnstedt,

Harth and

Polleres, Comparing data summaries for processing live queries over linked data, World Wide Web 14(5–6) (2011), 495–544.

66.

[66]

Umbrich,

Karnstedt,

Hogan and

J.X.

Parreira, Hybrid SPARQL queries: Fresh vs. fast results, in: The Semantic Web – ISWC 2012, Proc. of the 11th International Semantic Web Conference, Part I, Boston, MA, USA, November 11–15, 2012,

Cudré-Mauroux,

Heflin,

Sirin,

Tudorache,

Euzenat,

Hauswirth,

J.X.

Parreira,

Hendler,

Schreiber,

Bernstein and

Blomqvist, eds, Lecture Notes in Computer Science, Vol. 7649, Springer, 2012, pp. 608–624.

67.

[67]

Urbani,

Kotoulas,

Oren and

van Harmelen, Scalable distributed reasoning using mapreduce, in: Bernstein et al. [11], pp. 634–649.

68.

[68]

Weaver and

J.A.

Hendler, Parallel materialization of the finite RDFS closure for hundreds of millions of triples, in: Bernstein et al. [11], pp. 682–697.