资源论文Extending Decidable Existential Rules by Joining Acyclicity and Guardedness

Extending Decidable Existential Rules by Joining Acyclicity and Guardedness

2019-11-12 | |  44 |   34 |   0
Abstract Existential rules, i.e. Datalog extended with existential quanti?ers in rule heads, are currently studied under a variety of names such as Datalog+/–, ??-rules, and tuple-generating dependencies. The renewed interest in this formalism is fuelled by a wealth of recently discovered language fragments for which query answering is decidable. This paper extends and consolidates two of the main approaches in this ?eld – acyclicity and guardedness – by providing (1) complexity-preserving generalisations of weakly acyclic and weakly (frontier-)guarded rules, and (2) a novel formalism of glut-(frontier-)guarded rules that subsumes both. This builds on an insight that acyclicity can be used to extend any existential rule language while retaining decidability. Besides decidability, combined query complexities are established in all cases.

上一篇:On the Decidability of Connectedness Constraints in 2D and 3D Euclidean Spaces

下一篇:On the Progression of Knowledge in the Situation Calculus

用户评价
全部评价

热门资源

  • Learning to Predi...

    Much of model-based reinforcement learning invo...

  • Stratified Strate...

    In this paper we introduce Stratified Strategy ...

  • The Variational S...

    Unlike traditional images which do not offer in...

  • Learning to learn...

    The move from hand-designed features to learned...

  • A Mathematical Mo...

    Direct democracy, where each voter casts one vo...