Talks and Poster Presentations (with Proceedings-Entry):

M. Alviano, A. Pieris:
"Default Negation for Non-Guarded Existential Rules";
Talk: Symposium on Principles of Database Systems, PODS 2015, Melbourne, Victoria, Australia; 05-31-2015 - 06-04-2015; 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.

English abstract:
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

"Official" electronic version of the publication (accessed through its Digital Object Identifier - DOI)

Related Projects:
Project Head Reinhard Pichler:
Heterogene Information Integration

Project Head Reinhard Pichler:
SEE: SPARQL Evaluation and Extensions

Project Head Stefan Woltran:

Created from the Publication Database of the Vienna University of Technology.