Paper Info
Title
Well-founded semantics for extended datalog and ontological reasoning
Abstract
The Datalog± family of expressive extensions of Datalog has recently been introduced as a new paradigm for query answering over ontologies, which captures and extends several common description logics. It extends plain Datalog by features such as existentially quantified rule heads and, at the same time, restricts the rule syntax so as to achieve decidability and tractability. In this paper, we continue the research on Datalog±. More precisely, we generalize the well-founded semantics (WFS), as the standard semantics for nonmonotonic normal programs in the database context, to Datalog± programs with negation under the unique name assumption (UNA). We prove that for guarded Datalog± with negation under the standard WFS, answering normal Boolean conjunctive queries is decidable, and we provide precise complexity results for this problem, namely, in particular, completeness for PTIME (resp., 2-EXPTIME) in the data (resp., combined) complexity.
Year
DOI
Venue
2013
10.1145/2463664.2465229
Description Logics
Keywords
DocType
Citations 
standard semantics,standard wfs,precise complexity result,nonmonotonic normal program,ontological reasoning,normal boolean conjunctive query,rule head,extended datalog,guarded datalog,plain datalog,well-founded semantics,rule syntax,query answering
Conference
7
PageRank 
References 
Authors
0.52
9
4
Name
Order
Citations
PageRank
André Hernich1878.30
Clemens Kupke232125.20
Thomas Lukasiewicz32618165.18
Georg Gottlob495941103.48