Rewriting Guarded Negation Queries

Query optimizations are notoriously difficult for queries involving negation. Together with academic collaborator Professor Michael Benedikt of University of Oxford, LogicBlox team members Vince Barany and Balder ten Cate have been studying an interesting fragment of queries with negation, the Guarded Negation Fragment. They published their latest results in MFCS 2013, 38th International Symposium on Mathematical Foundations of Computer Science.  We look forward to applying this work in the optimization of LogicBlox queries!

Abstract The Guarded Negation Fragment (GNFO) is a fragment of first-order logic that contains all unions of conjunctive queries, a restricted form of negation that suffices for expressing some common uses of negation in SQL queries, and a large class of integrity constraints. At the same time, as was recently shown, the syntax of GNFO is restrictive enough so that static analysis problems such as query containment are still decidable. This suggests that, in spite of its expressive power, GNFO queries are amenable to novel optimizations. In this paper we provide further evidence for this, establishing that GNFO queries have distinctive features with respect to rewriting. Our results include effective preservation theorems for GNFO, Craig Interpolation and Beth Definability results, and the ability to express the certain answers of queries with respect to GNFO constraints within very restricted logics.


Leave a reply

©2017 LogicBlox

Log in with your credentials

Forgot your details?