Detecting Unsatisfiable Conjunctive Property Path Queries under Shape Expression Schema
Yuuki Maedaa, Nobutaka Suzuki · Chronicle of computing · 2022
Shape Expression (ShEx) is a novel schema language proposed for RDF/graph data. For a ShEx schema S and a query q, q is said to be unsatisfiable if for any valid data D under S q reports an empty answer over D. In general, the size of RDF/graph data is very large, and thus it is inefficient to perform unsatisfiable queries on such data. Therefore, it is desirable that we can detect unsatisfiable queries efficiently before executing them. In this paper, we consider Conjunctive Property Path, a generalization of Property Path defined in SPARQL 1.1, as the query language. First, we propose an algorithm for determining satisfiability of Conjunctive Property Path queries under ShEx schema. Then we conducted a preliminary experiment, which results suggest that the proposed algorithm determines if a given Conjunctive Property Path query is satisfiable efficiently.