# Tractable Query Answering and Optimization for Extensions of Weakly-Sticky Datalog+-

arXiv: https://arxiv.org/abs/1504.03386 · HTML: https://mlsanity.com/paper/1504.03386/

## Key facts

- Cited by 1 papers in the map (data through 14 Oct 2026).
- First posted on arXiv 13 Apr 2015.

## Built on by (most cited first, 1 of 1)

- [Extending Sticky-Datalog+/- via Finite-Position Selection Functions: Tractability, Algorithms, and Optimization](https://mlsanity.com/paper/2108.00903/) (2021)

## Abstract (arXiv)

We consider a semantic class, weakly-chase-sticky (WChS), and a syntactic subclass, jointly-weakly-sticky (JWS), of Datalog+- programs. Both extend that of weakly-sticky (WS) programs, which appear in our applications to data quality. For WChS programs we propose a practical, polynomial-time query answering algorithm (QAA). We establish that the two classes are closed under magic-sets rewritings. As a consequence, QAA can be applied to the optimized programs. QAA takes as inputs the program (including the query) and semantic information about the "finiteness" of predicate positions. For the syntactic subclasses JWS and WS of WChS, this additional information is computable.