Equality−Friendly Well−Founded Semantics and Applications to Description Logics
<p>We tackle the problem of defining a well-founded semantics for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a well-founded semantics (WFS) for the recent Datalog+/- family of ontology languages, which covers se...
| Main Authors: | , , , |
|---|---|
| Format: | Conference item |
| Published: |
AAAI Press
2012
|
| _version_ | 1797085247974670336 |
|---|---|
| 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 for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a well-founded semantics (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-07T02:06:16Z |
| format | Conference item |
| id | oxford-uuid:9f189536-a65e-43bf-b5bf-ae2858b5861c |
| institution | University of Oxford |
| last_indexed | 2024-03-07T02:06:16Z |
| publishDate | 2012 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | oxford-uuid:9f189536-a65e-43bf-b5bf-ae2858b5861c2022-03-27T00:54:56ZEquality−Friendly Well−Founded Semantics and Applications to Description LogicsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:9f189536-a65e-43bf-b5bf-ae2858b5861cDepartment of Computer ScienceAAAI Press2012Gottlob, GHernich, AKupke, CLukasiewicz, T<p>We tackle the problem of defining a well-founded semantics for Datalog rules with existentially quantified variables in their heads and negations in their bodies. In particular, we provide a well-founded semantics (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 |