dRDF: Entailment for Domain-Restricted RDF
Lecture notes in computer sciencePublished 23 May 2008Open access
Reinhard Pichler, Axel Polleres, Fang Wei, Stefan Woltran
Citations14
SJR quartileQ2
SJR score0.35
SNIP0.55
Generate an AI Snapshot to get a quick, structured summary of this paper.
Study Snapshot
ObjectiveStudy objective
MethodsResearch methodology
PopulationPopulation studied
Sample sizeSample sizes
OutcomesStudy outcomes here
ResultsStudy results comes here
LimitationsResearch study limitations comes here
A concise AI-generated summary of the paper will appear here once you click Generate AI Snapshot.
TL;DR
It is shown that the restriction of domains in dRDF raises the complexity of entailment from NP-to Π2P -completeness and it is proved that the entailment is tractable for unrestricted graphs and coNP-complete for domain-restricted graphs.
Abstract
We introduce domain-restricted RDF (dRDF) which allows to associate an RDF graph with a fixed, finite domain that interpretations for it may range over. We show that dRDF is a real extension of RDF and discuss impacts on the complexity of entailment in dRDF. The entailment problem represents the key reasoning task for RDF and is well known to be NP-complete. Remarkably, we show that the restriction of domains in dRDF raises the complexity of entailment from NP- to \({\Pi^P_2}\)-completeness. In order to lower complexity of entailment for both domain-restricted and unrestricted graphs, we take a closer look at the graph structure. For cases where the structure of RDF graphs is restricted via the concept of bounded treewidth, we prove that the entailment is tractable for unrestricted graphs and coNP-complete for domain-restricted graphs.
Keywords
Computer Science
Electronic Notes in Theoretical Computer ScienceParameterized Complexity
2,884 Citations2002Michael R. Fellows
Texts and monographs in computer scienceParameterized Complexity
2,505 Citations1999Rodney G. Downey, Michael R. Fellows
An approach to complexity theory which offers a means of analysing algorithms in terms of their tractability, and introduces readers to new classes of algorithms which may be analysed more precisely than was the case until now.
The Description Logic Handbook
1,884 Citations2009Franz Baader, Diego Calvanese +3 more
SIAM Journal on ComputingA Linear-Time Algorithm for Finding Tree-Decompositions of Small Treewidth
1,534 Citations1996Hans L. Bodlaender
ACM Transactions on Database SystemsSemantics and complexity of SPARQL
1,137 Citations2009Jorge Eduardo Pérez Pérez, Marcelo Arenas +1 more
This article identifies a large class of SPARQL patterns, defined by imposing a simple and natural syntactic restriction, where the query evaluation problem can be solved more efficiently and shows that the evaluation problem is coNP-complete for well-designed patterns.
Lecture notes in computer scienceDisjunctive Tautologies as Synchronisation Schemes
1,105 Citations2000Vincent Danos, Jean-Louis Krivine
In the ambient logic of classical second order propositional calculus, the specification problem for a family of excluded middle like tautologies is solved and these are shown to be realized by sequential simulations of specific communication schemes for which they provide a safe typing mechanism.
SSRN Electronic JournalDescription Logic Programs: Combining Logic Programs with Description Logic
810 Citations2003Benjamin N. Grosof, Ian Horrocks +2 more
Journal of Web SemanticsReducing OWL entailment to description logic satisfiability
387 Citations2004Ian Horrocks, Peter F. Patel‐Schneider
Lecture notes in computer scienceSemantics and Complexity of SPARQL
374 Citations2006Jorge Eduardo Pérez Pérez, Marcelo Arenas +1 more
Journal of Web SemanticsCompleteness, decidability and complexity of entailment for RDF Schema and a semantic extension involving the OWL vocabulary
317 Citations2005Herman J. ter Horst
It is proved that entailment for RDF Schema (RDFS) is decidable, NP-complete, and in P if the target graph does not contain blank nodes, and that consistency is in P.
Theoretical Computer ScienceConjunctive query containment revisited
312 Citations2000Chandra Chekuri, Anand Rajaraman
This work considers the problems of conjunctive query containment and minimization, and shows that these problems can be solved in polynomial time for the class of acyclic queries, and defines a parameter called query width that captures the “degree of cyclicity” of a query.
Foundations of semantic web databases
284 Citations2004Claudio Gutiérrez, Carlos Hurtado +1 more
This work proposes a query language with well-defined semantics and study the complexity of query processing, query containment, and simplification of answers, including computational aspects of testing entailment and redundancy.
DL + log : tight integration of description logics and disjunctive datalog
209 Citations2006Riccardo Rosati
DL +log is defined, a general framework for the integration of Description Logics and disjunctive Datalog rules that allows for a tighter form of integration between DL-KBs and Datalogs rules which overcomes the main representational limits of the approaches based on the safety condition.
Decidability and expressiveness aspects of logic queries
180 Citations1987Oded Shmueli
It is shown that H+ is more expressive than YE++ and that any H+ program can be transformed into an equivalent H+ program containing a single recursive predicate without using the equality or inequality operators.
Lecture notes in computer scienceMinimal Deductive Systems for RDF
144 Citations2007Sergio Muñoz, Jorge Eduardo Pérez Pérez +1 more
This paper presents a minimalist program for RDF, by showing how one can do without several predicates and keywords of the RDF Schema vocabulary, obtaining a simpler language which preserves the original semantics.
Journal of Logic and ComputationHyperresolution and automated model building
74 Citations1996Christian G. Fermüller
Lecture notes in computer scienceReasoning with Rules and Ontologies
64 Citations2006Thomas Eiter, Giovambattista Ianni +3 more
This paper will discuss nonmonotonic logic programs under the answer-set semantics as a possible formalism of choice for realizing the Rules Layer, and focus on description-logic programs (or dl-programs, for short), which realize a transparent integration of rules and ontologies supported by existing reasoning engines, based on the answer -set semantics.
Lecture notes in computer scienceRules with Contextually Scoped Negation
50 Citations2006Axel Polleres, Cristina Feier +1 more
This work proposes logic programs with contexts and scoped negation and discusses two possible semantics with desirable properties and argues that this class of logic programs can be viewed as a rule extension to a subset of RDF(S).
Theory and Practice of Logic ProgrammingGuarded hybrid knowledge bases
32 Citations2008Stijn Heymans, Jos de Bruijn +3 more
Lecture notes in computer scienceOn Representational Issues About Combinations of Classical Theories with Nonmonotonic Rules
27 Citations2006Jos de Bruijn, Thomas Eiter +2 more
This paper identifies fundamental representational issues which need to be addressed by such combinations and formulates a number of formal principles which help to characterize and classify existing and possible future approaches to the combination of rules and classical theories.
Machine Learning for Question Answering from Tabular Data
22 Citations2007Mahboob Alam Khalid, Valentin Jijkoun +1 more
A machine learning approach to querying tabular data for QA which is not restricted to specific domains is described and is shown to significantly outperform an existing rule-based table lookup method.
Lecture notes in computer scienceOn the Complexity of H-Subsumption
6 Citations1999Reinhard Pichler
It can be easily shown that H-subsumption may be incorporated as a redundancy deletion rule into many familiar (resolution- and paramodulation-based) inference systems without destroying the refutational completeness.