Edinburgh Research Explorer

The Impact of Active Domain Predicates on Guarded Existential Rules

Research output: Contribution to journalArticle

Related Edinburgh Organisations

Open Access permissions

Open

Documents

  • Download as Adobe PDF

    Rights statement: The final publication is available at IOS Press through http://dx.doi.org/10.3233/FI-2018-1660. https://www.iospress.nl/service/authors/author-copyright-agreement/

    Accepted author manuscript, 234 KB, PDF-document

https://content.iospress.com/articles/fundamenta-informaticae/fi1660?resultNumber=8&totalResults=191&start=0&q=gottlob&resultsPageSize=10&rows=10
Original languageEnglish
Pages (from-to)123-146
Number of pages22
JournalFundamenta Informaticae
Volume159
Issue number1-2
DOIs
Publication statusPublished - 7 Mar 2018

Abstract

It is realistic to assume that a database management system provides access to the active domain via built-in relations. Therefore, databases that include designated predicates that hold the active domain, which we call product databases, forma 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-based 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 query languages in question.

    Research areas

  • Rule-based languages, ontology-mediated queries, conjunctive queries, existential rules, tuple-generating dependencies, guardedness, expressive power, Complexity

Download statistics

No data available

ID: 37070136