[Back]

M. Alviano, A. Pieris:
"Default Negation for Non-Guarded Existential Rules";
Talk: Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia; 2015-05-31 - 2015-06-04; in: "Proceedings of the 34th ACM Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia, May 31 - June 4, 2015", T. Milo, D. Calvanese (ed.); ACM, (2015), ISBN: 978-1-4503-2757-2; 79 - 90.

The problem of query answering under the well-founded and stable model semantics for normal existential rules, that is, existential rules enriched with default negation, has recently attracted a lot of interest from the database and KR communities. In particular, it has been thoroughly studied for classes of normal existential rules that are based on restrictions that guarantee the tree-likeness of the underlying models; a prime example of such a restriction is guardedness. However, little is known about classes of existential rules that significantly deviate from the above paradigm. A prominent example of such a formalism is the class of existential rules that is based on the notion of stickiness, which enforces restrictions on the forms of joins in the rule-bodies. It is the precise aim of the current work to extend sticky existential rules with default negation, and perform an in-depth analysis of the complexity of conjunctive query answering under the well-founded and stable model semantics. We show that an effective way for bridging the gap between stickiness and the well-founded semantics exists, and we provide data and combined complexity results. However, there is no way to reconcile stickiness and the stable model semantics. The reason for this surprising negative result should be found in the fact that sticky existential rules are powerful enough for expressing cartesian products, a construct that forms a prime example of non-guardedness.

Query Answering; Datalog-based Languages; Default Negation; Well-founded Semantics; Stable Model Semantics; Complexity

http://dx.doi.org/10.1145/2745754.2745758

Project Head Reinhard Pichler:
Heterogene Information Integration

Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions

Project Head Stefan Woltran:
START