Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/21878
Title: | On the satisfiability problem for SPARQL patterns | Authors: | ZHANG, Xiaowang VAN DEN BUSSCHE, Jan Picalausa, François |
Issue Date: | 2016 | Source: | JOURNAL OF ARTIFICIAL INTELLIGENCE RESEARCH, 56, p. 403-428 | Abstract: | 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. | Notes: | Zhang, XW (reprint author), Tianjin Univ, Sch Comp Sci & Technol, Tianjin Key Lab Cognit Comp & Applicat, Tianjin, Peoples R China. xiaowangzhang@tju.edu.cn; jan.vandenbussche@uhasselt.be; fpicalausa@gmail.com | Document URI: | http://hdl.handle.net/1942/21878 | Link to publication/dataset: | http://www.jair.org/media/5028/live-5028-9408-jair.pdf | ISSN: | 1076-9757 | e-ISSN: | 1943-5037 | DOI: | 10.1613/jair.5028 | ISI #: | 000380245700001 | Rights: | © 2016 AI Access Foundation. All rights reserved | Category: | A1 | Type: | Journal Contribution | Validations: | ecoom 2017 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
live-5028-9408-jair.pdf | Published version | 354.39 kB | Adobe PDF | View/Open |
SCOPUSTM
Citations
13
checked on Sep 2, 2020
Page view(s)
64
checked on Sep 7, 2022
Download(s)
116
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.