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


© 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
Publication statusPublished - 2017
Externally publishedYes
EventLernen, Wissen, Daten, Analyse - 2017 Learning. Knowledge. Data. Analytics, LWDA 2017 - Rostock, Germany
Duration: 11 Sept 201713 Sept 2017

Publication series

NameCEUR Workshop Proceedings
ISSN (Print)1613-0073


ConferenceLernen, Wissen, Daten, Analyse - 2017 Learning. Knowledge. Data. Analytics, LWDA 2017


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

Cite this