Reconstructing graph pattern matches using SPARQL

S. Mennicke, D. Nagel, J.-C. Kalo, N. Aumann, W.-T. Balke

Research output: Chapter in Book / Report / Conference proceedingConference contributionAcademicpeer-review

Abstract

© 2017 by The Paper's Authors.Pattern matching is the foundation for handling complex queries to graph databases. Commonly used algorithms stem from the realm of graph isomorphism and simulations, being well understood theoretical frameworks. On the practical side, there are established graph query languages that often allow for a wide variety of query tasks, often even beyond pattern matching. However, very little is known how graph queries from common query languages relate to graph pattern matching relations. In this paper, we propose a study in this respect for SPARQL, the W3C recommendation for querying RDF data. The homomorphic nature of the SPARQL semantics allows for a straight-forward formulation of graph-isomorphic matching. However, the somewhat artificial nature of these queries motivates the study of sole basic graph patterns, the foundational concept of SPARQL. For basic graph patterns, we show a correspondence to strong simulation, an efficient graph pattern matching relation appreciated for its polynomial bound matches. In consequence, graph query languages are capable of serving as generating frameworks for established graph pattern matching relations.
Original languageEnglish
Title of host publicationLernen, Wissen, Daten, Analysen, LWDA 2017 - Conference Proceedings
EditorsM. Leyer
PublisherCEUR-WS
Pages152-164
Volume1917
Publication statusPublished - 2017
Externally publishedYes
EventLernen, Wissen, Daten, Analyse - 2017 Learning. Knowledge. Data. Analytics, LWDA 2017 - Rostock, Germany
Duration: 11 Sep 201713 Sep 2017

Publication series

NameCEUR Workshop Proceedings
ISSN (Print)1613-0073

Conference

ConferenceLernen, Wissen, Daten, Analyse - 2017 Learning. Knowledge. Data. Analytics, LWDA 2017
Country/TerritoryGermany
CityRostock
Period11/09/1713/09/17

Fingerprint

Dive into the research topics of 'Reconstructing graph pattern matches using SPARQL'. Together they form a unique fingerprint.

Cite this