Heba Aamer ; Bart Bogaerts ; Dimitri Surinx ; Eugenia Ternovska ; Jan Van den Bussche - Executable First-Order Queries in the Logic of Information Flows

lmcs:10121 - Logical Methods in Computer Science, May 8, 2024, Volume 20, Issue 2 - https://doi.org/10.46298/lmcs-20(2:6)2024
Executable First-Order Queries in the Logic of Information FlowsArticle

Authors: Heba Aamer ; Bart Bogaerts ; Dimitri Surinx ; Eugenia Ternovska ; Jan Van den Bussche

    The logic of information flows (LIF) has recently been proposed as a general framework in the field of knowledge representation. In this framework, tasks of procedural nature can still be modeled in a declarative, logic-based fashion. In this paper, we focus on the task of query processing under limited access patterns, a well-studied problem in the database literature. We show that LIF is well-suited for modeling this task. Toward this goal, we introduce a variant of LIF called "forward" LIF (FLIF), in a first-order setting. FLIF takes a novel graph-navigational approach; it is an XPath-like language that nevertheless turns out to be equivalent to the "executable" fragment of first-order logic defined by Nash and Ludäscher. One can also classify the variables in FLIF expressions as inputs and outputs. Expressions where inputs and outputs are disjoint, referred to as io-disjoint FLIF expressions, allow a particularly transparent translation into algebraic query plans that respect the access limitations. Finally, we show that general FLIF expressions can always be put into io-disjoint form.


    Volume: Volume 20, Issue 2
    Published on: May 8, 2024
    Accepted on: February 28, 2024
    Submitted on: October 5, 2022
    Keywords: Computer Science - Logic in Computer Science,H.2.3,I.2.4

    Consultation statistics

    This page has been seen 291 times.
    This article's PDF has been downloaded 168 times.