On the satisfiability problem for SPARQL patterns

DOI10.1613/JAIR.5028MaRDI QIDQ2818228zbMATH OpenOpenAlexWikidataFDO

Authors Xiaowang Zhang, Jan Van den Bussche, François Picalausa

Publication date 7 September 2016

Published in The Journal of Artificial Intelligence Research (JAIR) (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1406.1404

Mathematics Subject Classification ID

Data structures (68P05) Database theory (68P15) Logic in computer science (03B70)

Abstract: The satisfiability problem for SPARQL patterns is undecidable in general, since the expressive power of SPARQL 1.0 is comparable with that of the relational algebra. 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 efficiently decidable by simple checks on bound variables and on the use of literals. 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.

Recommendations

• Beyond well-designed SPARQL
• Complexity and expressive power of weakly well-designed SPARQL
• Querying incomplete information in RDF with SPARQL
• Testing satisfiability of a class of object-oriented conjunctive queries
• XPath satisfiability in the presence of DTDs

Cited in

(6)

• Satisfiability for SCULPT-schemas for CSV-like data
• On the relation between SPARQL1.1 and Answer Set Programming
• Implication and Axiomatization of Functional Constraints on Patterns with an Application to the RDF Data Model
• Complexity and expressive power of weakly well-designed SPARQL
• On the primitivity of operators in SPARQL
• Algebraic Structures for Capturing the Provenance of SPARQL Queries

This page was built for publication: On the satisfiability problem for SPARQL patterns

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2818228)