Subsumption of Weakly Well-Designed SPARQL Patterns is Undecidable
0
Citation
0
Reference
10
Related Paper
Abstract:
Weakly well-designed SPARQL patterns is a recent generalisation of well-designed patterns, which preserve good computational properties but also capture almost all patterns that appear in practice. Subsumption is one of static analysis problems for SPARQL, along with equivalence and containment. In this paper we show that subsumption is undecidable for weakly well-designed patterns, which is in stark contrast to well-designed patterns, and to equivalence and containment.Keywords:
Undecidable problem
Containment (computer programming)
Named graph
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.
Satisfiability
Boolean satisfiability problem
Named graph
Fragment (logic)
Cite
Citations (5)
Uniqueness of normal forms (UN=) is an important property of term rewrite systems. UN= is decidable for ground (i.e., variable-free) systems and undecidable in general. Recently it was shown to be decidable for linear, shallow systems. We generalize this previous result and show that this property is decidable for shallow rewrite systems, in contrast to confluence, reachability and other properties, which are all undecidable for flat systems. Our result is also optimal in some sense, since we prove that the UN= property is undecidable for two superclasses of flat systems: left-flat, left-linear systems in which right-hand sides are of depth at most two and right-flat, right-linear systems in which left-hand sides are of depth at most two.
Undecidable problem
Confluence
Reachability problem
Cite
Citations (3)
SPARQL (SPARQL Protocol and RDF Query Language) is a protocol and a request language which supports semantics of the RDF (Resource Description Framework) data. Based on previous research works, we noticed different lacks such as a poor flexibility when faced with functional and technical changes. According to first results, we aim to propose, depending on changing context including profile and location, suitable ontologies which can be accessed ‘upon request’. However, SPARQL queries are not able to take into account the users’ requirements update and their contexts changes as well. Faced to this limitation, we propose to use aspect paradigm to extend SPARQL and to promote adaptable SPARQL queries. Consequently, the ontologies of the project are invoked by adaptable SPARQL queries. We propose a genuine implementation in this paper.
Named graph
RDF Schema
RDF query language
Linked Data
Cite
Citations (0)
A decidable problem can be as hard as an undecidable one for all practical purposes. So what is the value of a mere decidability result? That is the topic discussed in the paper.
Undecidable problem
Value (mathematics)
Cite
Citations (3)
SPARQL is the W3C recommended querying language for RDF and OWL databases. It is designed for use at the global data on the Web, and thus enables queries over strewn data sources, independent of format. Due to unanticipated data sources, it is easier to extend the SPARQL queries. This paper briefly describes about the variants of SPARQL which have been designed to enhance its capabilities in various domains. The present list of variants includes SPARQL-DL, nSPARQL, iSPARQL, SPARQL++, PSPARQL, and SPARQL-ST. In this paper we present a comparative study between these variants on the basis of their performance, expressiveness, ease of implementation, inter and backward compatibility.
Named graph
Linked Data
RDF Schema
Cite
Citations (10)
This paper is primarily concerned with the following question which first appeared in Koenigsmann’s On a Question of Abraham Robinson’s: Is a finite field extension of a decidable field always decidable? This offers a “twist” to a question that was originally posed by Abraham Robinson in 1973 which had asked whether every finitely generated extension of an undecidable field remains undecidable. The above-mentioned work of Koenigsmann from 2016 (and independently, a result of Cherlin, van den Dries, and Macintyre much earlier in the 1980s) showed that there are indeed undecidable fields which admit decidable finite extensions. This paper aims to show that one could, similarly, find examples of decidable fields which admit undecidable finite extensions, thereby answering the above-stated question negatively. This result is achieved by identifying a sufficient condition which a decidable field must satisfy in order for it to have an undecidable finite extension. In an earlier iteration of this work, we had pointed out what we had believed to be one such condition. Unfortunately, this turned out not to be the case, which we illustrate using an explicit example. Through this demonstration, we were able to accentuate the weakness of the formerly mentioned criterion, which we strengthen in this thesis. We provide justification that the strengthened criterion is indeed sufficient – any decidable field satisfying this strengthened criterion would form a counterexample to the above-mentioned question. We study one such class of decidable fields, known as the wonderful extensions of the rational numbers, first introduced by Ershov in the early 2000s, whose (sufficiently saturated) elementary extensions satisfy this strengthened criterion. This provides us with a concrete counterexample which shows that there are indeed decidable fields which admit undecidable finite extensions. We also point out various attempts at finding other counterexamples to the above-mentioned question, the difficulties faced in those instances, and some further questions in the flavour of the above-mentioned question that appear to be interesting in their own rights.
Undecidable problem
Counterexample
Cite
Citations (0)
Undecidable problem
Decision problem
Cite
Citations (0)
There are a number of open problems involving the concepts of decidability and essential undecidability . This paper will present solutions to some of these problems. Specifically: (1) Can a decidable theory have an essentially undecidable, axiomatizable extension (with the same constants)? (2) Are all the complete extensions of an undecidable theory ever decidable? We shall show that the answer to both questions is in the affirmative. In answering question (1), the decidable theory for which an essentially undecidable axiomatizable extension will be constructed is the theory of the successor function and a single one-place predicate. It will also be shown that the decidability of this theory is a “best possible” result in the following direction: the theory of either of the common diadic arithmetic functions and a one-place predicate; i.e., of addition and a one-place predicate, or of multiplication and a one-place predicate, is undecidable. Before establishing the main result, it is convenient to give a simple proof that a decidable theory can have an axiomatizable (simply) undecidable extension. This is, of course, an immediate consequence of the main result; but the proof is simple and illustrates the methods that we are going to use in this paper.
Undecidable problem
Predicate (mathematical logic)
Model Theory
Cite
Citations (65)