Arrow Research search

Author name cluster

François Picalausa

Possible papers associated with this exact author name in Arrow. This page groups case-insensitive exact name matches and is not a full identity disambiguation profile.

2 papers
1 author row

Possible papers

2

JAIR Journal 2016 Journal Article

On the Satisfiability Problem for SPARQL Patterns

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

The satisfiability problem for SPARQL 1.0 patterns is undecidable in general, since the relational algebra can be emulated using such patterns. The goal of this paper is to delineate the boundary of decidability of satisfiability in terms of the constraints allowed in filter conditions. The classes of constraints considered are bound-constraints, negated bound- constraints, equalities, nonequalities, constant-equalities, and constant-nonequalities. The main result of the paper can be summarized by saying that, as soon as inconsistent filter conditions can be formed, satisfiability is undecidable. The key insight in each case is to find a way to emulate the set difference operation. Undecidability can then be obtained from a known undecidability result for the algebra of binary relations with union, composition, and set difference. When no inconsistent filter conditions can be formed, satisfiability is decidable by syntactic checks on bound variables and on the use of literals. Although the problem is shown to be NP-complete, it is experimentally shown that the checks can be implemented efficiently in practice. The paper also points out that satisfiability for the so-called 'well-designed' patterns can be decided by a check on bound variables and a check for inconsistent filter conditions.

PDF Details DOI

Highlights Conference 2016 Conference Abstract

On the satisfiability problem for SPARQL patterns

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

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.

Details
v2026.09.13