On the satisfiability problem for SPARQL patterns

Introduction SPARQL is the standard query language for data in RDF, in turn the standard data format for the Semantic Web. There are some significant differences between SPARQL and the relational algebra for the classical relational data model. First, queries do not access relations directly but rather perform pattern matching on RDF triples. Patterns may match only partially, so that the result of a query is a heterogeneous relation; different tuples in the result may be defined on different sets of variables. Such partial matching is made possible by the OPTIONAL operator. Relationally, OPTIONAL may be viewed as an outer join operator. The classical natural join operator is present in SPARQL as well. In contrast, set difference, or another explicit form of negation, was absent in the original design of SPARQL. The only feature that comes close to negation are negated bound constraints: the ability to express the condition that a certain variable from the pattern is not matched. Whereas an explicit difference operator (MINUS) was later added in version 1. 1 of SPARQL, researchers have been interested in investigating the theoretical foundations of the original SPARQL language [PAG09, AP11, AFK+16, KK16]. We are intrigued by this language as a new, heterogeneous variant of the classical relational algebra that gives equal weight to outer join and natural join. Indeed, while there already existed studies focusing on outer join in the relational setting [GLR97], the expressive power of outer join in interplay with other query operators has only become a research topic thanks to the new SPARQL context. Results We have investigated the decidability of the satisfiability problem for SPARQL patterns. Our starting point is the known observation that MINUS can already be expressed in basic SPARQL by exploiting negated bound constraints [AP11]. So, the addition of MINUS in SPARQL 1. 1 is just syntactic sugar. As a consequence, basic SPARQL has the full power of relational algebra and satisfiability if undecidable. We want to understand what happens when the use of constraints in patterns is restricted. We distinguish six kinds of constraints: equalities, constant-equalities, bound constraints, and their respective negations. Our main result is that as soon as inconsistent constraints can be formulated, satisfiability becomes undecidable. So, not only negated bound constraints, but also conjunctions of equalities and inequalities, or just constant equalities by themselves, already cause undecidability. Indeed, we show that MINUS can also be expressed using these constraints instead of negated bound constraints. Conversely, when inconsistent constraints cannot be formulated, satisfiability is shown to be decidable, and a finite model property is observed. The problem is NP-complete, even in the simple case of OPTIONAL-free patterns that use only bound constraints. In the special case of well-designed SPARQL patterns [PAG09], satisfiability is also decidable and in polynomial time. This is joint work with Xiaowang Zhang and François Picalausa. A full article on this research has recently been accepted (pending minor revisions) in the Journal of Artificial Intelligence Research. References [AFK+16] S. Ahmetaj, W. Fischl, M. Kr ̈oll, R. Pichler, M. Sˇimkus, and S. Skritek. The challenge of optional matching in SPARQL. In M. Gyssens and G. Simari, editors, Proceedings 9th International Symposium on Foundations of Information and Knowledge Systems, volume 9616 of Lecture Notes in Computer Science, pages 169–190, 2016. [AP11] M. Arenas and J. P ́erez. Querying semantic web data with SPARQL. In Proceedings 30st ACM Symposium on Principles of Databases, pages 305–316. ACM, 2011. [GLR97] C. Galindo-Legaria and A. Rosenthal. Outerjoin simplification and reordering for query optimization. ACM Transactions on Database Systems, 22(1): 43–74, 1997. [KK16] M. Kaminski and E. V. Kostylev. Beyond well-designed SPARQL. In Proceedings 19th International Conference on Database Theory, 2016. [PAG09] J. P ́erez, M. Arenas, and C. Gutierrez. Semantics and complexity of SPARQL. ACM Transactions on Database Systems, 34(3): article 16, 2009.

Authors

• Jan Van den Bussche
• Xiaowang Zhang Tianjin University
• François Picalausa

Keywords

No keywords are indexed for this paper.