Extending sticky-Datalog± via finite-position selection functions: Tractability, algorithms, and optimization. Issue 114 (March 2023)

• Record Type: Journal Article
• Authors: Bertossi, Leopoldo; Milani, Mostafa
• Is Part Of: Information systems. Issue 114(2023)
• Publication Date: 2023-03
• Subjects: Datalog± -- Query answering and reasoning -- Ontology-based data access; Database management -- Periodicals; Electronic data processing -- Periodicals; Bases de données -- Gestion -- Périodiques; Informatique -- Périodiques; Database management; Electronic data processing; Periodicals; 005.7
• DOI: 10.1016/j.is.2022.102156
• Languages: English
• ISSNs: 0306-4379

Abstract

Abstract: 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 many 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 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 (in data complexity). 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 . Highlights: Weakly-sticky Datalog ± is an expressive class of programs based on the conditions of weakacyclicity and stickiness. Query answering is tractable for weakly-sticky programs. Magic-set rewriting optimizes query answering over Datalog ± programs. Weakly-sticky Datalog ± class is not closed under magic-set rewriting. Jointly-weakly-sticky programs extends weakly-sticky programs. Jointly-weakly-sticky programs allows tractable query answering and is closed under magic-sets rewriting.