# Extending Sticky-Datalog+/- via Finite-Position Selection Functions: Tractability, Algorithms, and Optimization

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

## Key facts

- No citing papers in the map yet (data through 14 Oct 2026).
- Builds on 8 of its 41 references that are in the map.
- First posted on arXiv 2 Aug 2021.

## Builds on (most cited first, 8 of 8)

- [The Vadalog System: Datalog-based Reasoning for Knowledge Graphs](https://mlsanity.com/paper/1807.08709/) (2018)
- [The DL-Lite Family and Relations](https://mlsanity.com/paper/1401.3487/) (2014)
- [Query Rewriting and Optimization for Ontological Databases](https://mlsanity.com/paper/1405.2848/) (2014)
- [Fixpoint Semantics and Optimization of Recursive Datalog Programs with Aggregates](https://mlsanity.com/paper/1707.05681/) (2017)
- [Ontological Multidimensional Data Models and Contextual Data Qality](https://mlsanity.com/paper/1704.00115/) (2017)
- [Datalog: Bag Semantics via Set Semantics](https://mlsanity.com/paper/1803.06445/) (2018)
- [Tractable Query Answering and Optimization for Extensions of Weakly-Sticky Datalog+-](https://mlsanity.com/paper/1504.03386/) (2015)
- [Extending Weakly-Sticky Datalog+/-: Query-Answering Tractability and Optimizations](https://mlsanity.com/paper/1607.02682/) (2016)

## Abstract (arXiv)

Weakly-Sticky(WS) Datalog+/- is an expressive member of the family of Datalog+/- program classes that is defined on the basis of the conditions of stickiness and weak-acyclicity. Conjunctive query answering (QA) over the WS programs has been investigated, and its tractability in data complexity has been established. However, the design and implementation of practical QA algorithms and their optimizations have been open. In order to fill this gap, we first study Sticky and WS programs from the point of view of the behavior of the chase procedure. We extend the stickiness property of the chase to that of generalized stickiness of the chase (GSCh) modulo an oracle that selects (and provides) the predicate positions where finitely values appear during the chase. Stickiness modulo a selection function S that provides only a subset of those positions defines sch(S), a semantic subclass of GSCh. Program classes with selection functions include Sticky and WS, and another syntactic class that we introduce and characterize, namely JWS, of jointly-weakly-sticky programs, which contains WS. The selection functions for these last three classes are computable, and no external, possibly non-computable oracle is needed. We propose a bottom-up QA algorithm for programs in the class sch(S), for a general selection function S. As a particular case, we obtain a polynomial-time QA algorithm for JWS and weakly-sticky programs. Unlike WS, JWS turns out to be closed under magic-sets query optimization. As a consequence, both the generic polynomial-time QA algorithm and its magic-set optimization can be particularized and applied to WS.