Equality−Friendly Well−Founded Semantics and Applications to Description Logics
<p>We tackle the problem of defining a well-founded semantics (WFS) for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a WFS for the recent Datalog family of ontology languages, which covers several important descript...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
CEUR−WS.org
2012
|
| _version_ | 1826296999669923840 |
|---|---|
| author | Gottlob, G Hernich, A Kupke, C Lukasiewicz, T |
| author_facet | Gottlob, G Hernich, A Kupke, C Lukasiewicz, T |
| author_sort | Gottlob, G |
| collection | OXFORD |
| description | <p>We tackle the problem of defining a well-founded semantics (WFS) for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a WFS for the recent Datalog family of ontology languages, which covers several important description logics (DLs). To do so, we generalize Datalog by non-stratified nonmonotonic negation in rule bodies, and we define a WFS for this generalization via guarded fixed point logic. We refer to this approach as equality-friendly WFS, since it has the advantage that it does not make the unique name assumption (UNA); this brings it close to OWL and its profiles as well as typical DLs, which also do not make the UNA. We prove that for guarded Datalog with negation under the equality-friendly WFS, conjunctive query answering is decidable, and we provide precise complexity results for this problem. From these results, we obtain precise definitions of the standard WFS extensions of EL and of members of the DL-Lite family, as well as corresponding complexity results for query answering.</p> |
| first_indexed | 2024-03-07T04:24:56Z |
| format | Conference item |
| id | oxford-uuid:cc4b930b-7cfe-4784-954f-1227ada13e15 |
| institution | University of Oxford |
| last_indexed | 2024-03-07T04:24:56Z |
| publishDate | 2012 |
| publisher | CEUR−WS.org |
| record_format | dspace |
| spelling | oxford-uuid:cc4b930b-7cfe-4784-954f-1227ada13e152022-03-27T07:20:55ZEquality−Friendly Well−Founded Semantics and Applications to Description LogicsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:cc4b930b-7cfe-4784-954f-1227ada13e15Department of Computer ScienceCEUR−WS.org2012Gottlob, GHernich, AKupke, CLukasiewicz, T<p>We tackle the problem of defining a well-founded semantics (WFS) for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a WFS for the recent Datalog family of ontology languages, which covers several important description logics (DLs). To do so, we generalize Datalog by non-stratified nonmonotonic negation in rule bodies, and we define a WFS for this generalization via guarded fixed point logic. We refer to this approach as equality-friendly WFS, since it has the advantage that it does not make the unique name assumption (UNA); this brings it close to OWL and its profiles as well as typical DLs, which also do not make the UNA. We prove that for guarded Datalog with negation under the equality-friendly WFS, conjunctive query answering is decidable, and we provide precise complexity results for this problem. From these results, we obtain precise definitions of the standard WFS extensions of EL and of members of the DL-Lite family, as well as corresponding complexity results for query answering.</p> |
| spellingShingle | Gottlob, G Hernich, A Kupke, C Lukasiewicz, T Equality−Friendly Well−Founded Semantics and Applications to Description Logics |
| title | Equality−Friendly Well−Founded Semantics and Applications to Description Logics |
| title_full | Equality−Friendly Well−Founded Semantics and Applications to Description Logics |
| title_fullStr | Equality−Friendly Well−Founded Semantics and Applications to Description Logics |
| title_full_unstemmed | Equality−Friendly Well−Founded Semantics and Applications to Description Logics |
| title_short | Equality−Friendly Well−Founded Semantics and Applications to Description Logics |
| title_sort | equality friendly well founded semantics and applications to description logics |
| work_keys_str_mv | AT gottlobg equalityfriendlywellfoundedsemanticsandapplicationstodescriptionlogics AT hernicha equalityfriendlywellfoundedsemanticsandapplicationstodescriptionlogics AT kupkec equalityfriendlywellfoundedsemanticsandapplicationstodescriptionlogics AT lukasiewiczt equalityfriendlywellfoundedsemanticsandapplicationstodescriptionlogics |