Complexity of well-designed SPARQL

Abstract

SPARQL Protocol and RDF Query Language (SPARQL) ist eine standardisierte Möglichkeit um Resource Description Framework (RDF) Daten aus dem Internet abzufragen. Ein Feature von SPARQL 1.0 ist der GRAPH Operator, der es erlaubt, mehrere lokale RDF Graphen in einer einzigen SPARQL Query zu verwenden. Mit der Zeit tauchten immer mehr SPARQL Schnittstellen im Internet auf und um jene auch ansprechen zu können, wurde der SERVICE Operator in der SPARQL 1.1 Federated Query extension eingeführt. Mit dem SERVICE Operator kann man, ähnlich dem GRAPH Operator, mehrere SPARQL Endpoints in einer Query benützen. Sowohl der GRAPH Operator als auch der SERVICE Operator werfen neue Probleme in der Komplexitätsanalyse von SPARQL auf. Die beiden Operatoren wurden bis jetzt noch nicht analysiert. Weil die Evaluierung von allgemeinen SPARQL Queries PSPACE-complete ist, beschränken wir unsere Beobachtungen auf well-designed SPARQL, wo das Evaluierungsproblem coNP-complete ist. Wenn man das well-designed SPARQL Fragment mit SERVICE und GRAPH erweitert, erhält man ein neues SPARQL Fragment welches eine gute Basis für unsere Komplexitätsanalyse darstellt. Wenn man allgemeines SPARQL um die beiden Operatoren erweitern würde, könnte es sein, dass die Komplexität der beiden Operatoren von diesem Fragment überschattet würden. Wir werden zeigen, dass die Komplexität des Evaluierungsproblems im well-designed Fragment, welches mit den Operatoren GRAPH und SERVICE erweitert wurde, coNP-complete ist. Wenn man den SERVICE operator in der Praxis benutzt, löst dieser neue Schwierigkeiten aus, die mit der Einführung mehrerer Notationen gelöst wurden. Der Unterschied dieser Notationen wurde bis jetzt noch nicht wirklich erforscht. Nachdem wir die Notationen eingeführt haben, werden wir sie diskutieren. Wir werden auch das Fragment weakly well-designed SPARQL behandeln. Es ist ein auf well-designed SPARQL basierendes Fragment, welches allerdings mächtiger ist, weil es einige Bedingungen des well-designed SPARQL Fragments schwächt.

The SPARQL Protocol and RDF Query Language (SPARQL) presents a standardized way to query the growing amount of Resource Description Framework (RDF) data on the internet. A feature of SPARQL 1.0 is the GRAPH operator which is able to query multiple local RDF graphs in only a single query. To access the growing amounts of SPARQL endpoints available on the internet, the SERVICE operator was introduced in the SPARQL 1.1 Federated Query extension. The SERVICE operator is used to query several SPARQL endpoints in only a single query, similar to the GRAPH operator. Both the SERVICE and the GRAPH operator pose new problems in the complexity analysis of SPARQL, as the two operators have not yet been analyzed. Because the evaluation of general SPARQL patterns is PSPACE-complete we restrict our considerations to well-designed SPARQL, where the evaluation problem is coNP-complete. Extending the well-designed fragment of SPARQL with the SERVICE and GRAPH operators yields a new SPARQL fragment which is a good basis for a complexity analysis, as general SPARQLwouldcloudthecomplexityoftheSERVICEandGRAPHoperators. Itisshown that the evaluation problem in this fragment is coNP-complete. Using the SERVICE operator in practice elicits di-culties which were resolved by introducing various notions. Thesubtledi-erencebetweenthosenotionshasnotyetbeenfullyexplored. Afterde-ning the notions the di-erences between them will be discussed. Building upon well-designed SPARQL we will also cover weakly well-designed SPARQL which renders a powerful fragment by relaxing constraints of well-designed SPARQL.