Projects per year
Abstract / Description of output
Normal tuplegenerating dependencies (NTGDs) are TGDs enriched with default negation, a.k.a. negation as failure. Query answering under NTGDs, where negation is interpreted according to the stable model semantics, is an intriguing new problem that gave rise to flourishing research activity in the database and KR communities. So far, all the existing works that investigate this problem, except for one recent paper that adopts an operational semantics based on the chase, follow the socalled logic programming (LP) approach. According to the LP approach, the existentially quantified variables are first eliminated via Skolemization, which leads to a normal logic program, and then the standard stable model semantics for normal logic programs is applied. However, as we discuss in the paper, Skolemization is not appropriate in the presence of default negation since it fails to capture the intended meaning of NTGDs, while the operational semantics mentioned above fails to overcome the limitations of the LP approach. This reveals the need to adopt an alternative approach to stable model semantics that is directly applicable to NTGDs with existentially quantified variables. We propose such an approach based on a recent characterization
of stable models in terms of secondorder logic, which indeed overcomes the limitations of the LP approach. We then perform an indepth complexity analysis of query answering under prominent classes of NTGDs based on the main decidability paradigms for TGDs, namely weakacyclicity, guardedness and stickiness. Interestingly, weaklyacyclic NTGDs give rise to robust and highly
expressive query languages that allow us to solve in a declarative way problems in the second level of the polynomial hierarchy.
of stable models in terms of secondorder logic, which indeed overcomes the limitations of the LP approach. We then perform an indepth complexity analysis of query answering under prominent classes of NTGDs based on the main decidability paradigms for TGDs, namely weakacyclicity, guardedness and stickiness. Interestingly, weaklyacyclic NTGDs give rise to robust and highly
expressive query languages that allow us to solve in a declarative way problems in the second level of the polynomial hierarchy.
Original language  English 

Title of host publication  PODS '17 Proceedings of the 36th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems 
Publisher  ACM 
Pages  377388 
Number of pages  12 
ISBN (Print)  9781450341981 
DOIs  
Publication status  Published  9 May 2017 
Event  36th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems  New York, United States Duration: 14 May 2017 → 19 May 2017 
Conference
Conference  36th ACM SIGMODSIGACTSIGAI Symposium on Principles of Database Systems 

Country/Territory  United States 
City  New York 
Period  14/05/17 → 19/05/17 
Fingerprint
Dive into the research topics of 'Stable Model Semantics for TupleGenerating Dependencies Revisited'. Together they form a unique fingerprint.Projects
 1 Finished

VADA: Value Added Data Systems: Principles and Architecture
Libkin, L., Buneman, P., Fan, W. & Pieris, A.
1/04/15 → 30/09/20
Project: Research