Edinburgh Research Explorer

Stable Model Semantics for Tuple-Generating Dependencies Revisited

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

http://dl.acm.org/citation.cfm?doid=3034786.3034794
Original languageEnglish
Title of host publicationPODS '17 Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
PublisherACM
Pages377-388
Number of pages12
ISBN (Print)978-1-4503-4198-1
DOIs
Publication statusPublished - 9 May 2017
Event36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems - New York, United States
Duration: 14 May 201719 May 2017

Conference

Conference36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
CountryUnited States
CityNew York
Period14/05/1719/05/17

Abstract

Normal tuple-generating 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 so-called 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 second-order logic, which indeed overcomes the limitations of the LP approach. We then perform an in-depth complexity analysis of query answering under prominent classes of NTGDs based on the main decidability paradigms for TGDs, namely weak-acyclicity, guardedness and stickiness. Interestingly, weakly-acyclic 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.

Event

36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems

14/05/1719/05/17

New York, United States

Event: Conference

Download statistics

No data available

ID: 31832884