Please use this identifier to cite or link to this item:
http://hdl.handle.net/1942/28418
Title: | On the Satisfiability Problem of Patterns in SPARQL 1.1 | Authors: | ZHANG, Xiaowang VAN DEN BUSSCHE, Jan Wang, Kewen Wang, Zhe |
Issue Date: | 2018 | Publisher: | ASSOC ADVANCEMENT ARTIFICIAL INTELLIGENCE | Source: | AAAI Publications, Thirty-Second AAAI Conference on Artificial Intelligence,p. 2054-2061 | Abstract: | The pattern satisfiability is a fundamental problem for SPARQL. This paper provides a complete analysis of decidability/undecidability of satisfiability problems for SPARQL 1.1 patterns. A surprising result is the undecidability of satisfiability for SPARQL 1.1 patterns when only AND and MINUS are expressible. Also, it is shown that any fragment of SPARQL 1.1 without expressing both AND and MINUS is decidable. These results provide a guideline for future SPARQL query language design and implementation. | Notes: | Zhang, XW (reprint author), Tianjin Univ, Sch Comp Sci & Technol, Tianjin, Peoples R China. Tianjin Key Lab Cognit Comp & Applicat, Tianjin, Peoples R China. | Document URI: | http://hdl.handle.net/1942/28418 | Link to publication/dataset: | https://www.aaai.org/ocs/index.php/AAAI/AAAI18/paper/view/16590 | ISBN: | 9781577358008 | ISI #: | WOS:000485488902016 | Category: | C1 | Type: | Proceedings Paper | Validations: | ecoom 2020 |
Appears in Collections: | Research publications |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
16590-76673-1-PB.pdf Restricted Access | Published version | 527.48 kB | Adobe PDF | View/Open Request a copy |
WEB OF SCIENCETM
Citations
3
checked on May 2, 2024
Page view(s)
18
checked on Sep 7, 2022
Download(s)
6
checked on Sep 7, 2022
Google ScholarTM
Check
Altmetric
Items in DSpace are protected by copyright, with all rights reserved, unless otherwise indicated.