The Impact of Active Domain Predicates on Guarded Existential Rules
We claim it is realistic to assume that a database management system provides access to the active domain via built-in relations. Therefore, product databases, i.e., databases that include designated predicates that hold the active domain, form a natural notion that deserves our attention. An import...
| Hauptverfasser: | , , |
|---|---|
| Format: | Conference item |
| Veröffentlicht: |
Springer Verlag
2016
|
| _version_ | 1826265904913055744 |
|---|---|
| author | Gottlob, G Pieris, A Ŝimkus, M |
| author_facet | Gottlob, G Pieris, A Ŝimkus, M |
| author_sort | Gottlob, G |
| collection | OXFORD |
| description | We claim it is realistic to assume that a database management system provides access to the active domain via built-in relations. Therefore, product databases, i.e., databases that include designated predicates that hold the active domain, form a natural notion that deserves our attention. An important issue then is to look at the consequences of product databases for the expressiveness and complexity of central existential rule languages. We focus on guarded existential rules, and we investigate the impact of product databases on their expressive power and complexity. We show that the queries expressed via (frontier-)guarded rules gain in expressiveness, and in fact, they have the same expressive power as Datalog. On the other hand, there is no impact on the expressiveness of the queries specified via weakly-(frontier-)guarded rules since they are powerful enough to explicitly compute the predicates needed to access the active domain. We also observe that there is no impact on the complexity of the languages in question. |
| first_indexed | 2024-03-06T20:30:54Z |
| format | Conference item |
| id | oxford-uuid:31005bd2-d112-4f8e-992e-0e5e9e4d72c8 |
| institution | University of Oxford |
| last_indexed | 2024-03-06T20:30:54Z |
| publishDate | 2016 |
| publisher | Springer Verlag |
| record_format | dspace |
| spelling | oxford-uuid:31005bd2-d112-4f8e-992e-0e5e9e4d72c82022-03-26T13:05:09ZThe Impact of Active Domain Predicates on Guarded Existential RulesConference itemhttp://purl.org/coar/resource_type/c_5794uuid:31005bd2-d112-4f8e-992e-0e5e9e4d72c8Symplectic Elements at OxfordSpringer Verlag2016Gottlob, GPieris, AŜimkus, MWe claim it is realistic to assume that a database management system provides access to the active domain via built-in relations. Therefore, product databases, i.e., databases that include designated predicates that hold the active domain, form a natural notion that deserves our attention. An important issue then is to look at the consequences of product databases for the expressiveness and complexity of central existential rule languages. We focus on guarded existential rules, and we investigate the impact of product databases on their expressive power and complexity. We show that the queries expressed via (frontier-)guarded rules gain in expressiveness, and in fact, they have the same expressive power as Datalog. On the other hand, there is no impact on the expressiveness of the queries specified via weakly-(frontier-)guarded rules since they are powerful enough to explicitly compute the predicates needed to access the active domain. We also observe that there is no impact on the complexity of the languages in question. |
| spellingShingle | Gottlob, G Pieris, A Ŝimkus, M The Impact of Active Domain Predicates on Guarded Existential Rules |
| title | The Impact of Active Domain Predicates on Guarded Existential Rules |
| title_full | The Impact of Active Domain Predicates on Guarded Existential Rules |
| title_fullStr | The Impact of Active Domain Predicates on Guarded Existential Rules |
| title_full_unstemmed | The Impact of Active Domain Predicates on Guarded Existential Rules |
| title_short | The Impact of Active Domain Predicates on Guarded Existential Rules |
| title_sort | impact of active domain predicates on guarded existential rules |
| work_keys_str_mv | AT gottlobg theimpactofactivedomainpredicatesonguardedexistentialrules AT pierisa theimpactofactivedomainpredicatesonguardedexistentialrules AT simkusm theimpactofactivedomainpredicatesonguardedexistentialrules AT gottlobg impactofactivedomainpredicatesonguardedexistentialrules AT pierisa impactofactivedomainpredicatesonguardedexistentialrules AT simkusm impactofactivedomainpredicatesonguardedexistentialrules |