The space-efficient core of Vadalog

Journal article

Vadalog is a system for performing complex reasoning tasks such as those required in advanced knowledge graphs. The logical core of the underlying Vadalog language is the warded fragment of tuple-generating dependencies (TGDs). This formalism ensures tractable reasoning in data complexity, while a recent analysis focusing on a practical implementation led to the reasoning algorithm around which the Vadalog system is built. A fundamental question that has emerged in the context of Vadalog is whether we can limit the recursion allowed by wardedness in order to obtain a formalism that provides a convenient syntax for expressing useful recursive statements, and at the same time achieves space-efficiency. After analyzing several real-life examples of warded sets of TGDs provided by our industrial partners, as well as recent benchmarks, we observed that recursion is often used in a restricted way: the body of a TGD contains at most one atom whose predicate is mutually recursive with a predicate in the head. We show that this type of recursion, known as piece-wise linear in the Datalog literature, is the answer to our main question. We further show that piece-wise linear recursion alone, without the wardedness condition, is not enough as it leads to undecidability. We also study the relative expressiveness of the query languages based on (piece-wise linear) warded sets of TGDs. Finally, we give preliminary experimental evidence for the practical effect of piece-wise linearity on Vadalog.

Authors: Berger, G; Gottlob, G; Pieris, A; Sallinger, E

• Publication status: Published
• Peer review status: Peer reviewed
• Publisher: Association for Computing Machinery
• Journal: ACM Transactions on Database Systems
• Volume: 47
• Issue: 1
• Pages: 1-46
• Publication date: 2022-04-06
• Acceptance date: 2021-09-01
• DOI: 10.1145/3488720
• EISSN: 1557-4644
• ISSN: 0362-5915
• Language: English
• Keywords: FFR