Edinburgh Research Explorer

The Space-Efficient Core of Vadalog

Research output: Chapter in Book/Report/Conference proceedingConference contribution

Related Edinburgh Organisations

Open Access permissions

Open

Documents

https://dl.acm.org/citation.cfm?doid=3294052.3319688
Original languageEnglish
Title of host publicationPODS '19 Proceedings of the 38th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of Database Systems
Place of PublicationNew York
PublisherACM
Pages270-284
Number of pages15
ISBN (Print)978-1-4503-6227-6
DOIs
Publication statusE-pub ahead of print - 25 Jun 2019
EventACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019) - Amsterdam, Netherlands
Duration: 30 Jun 20195 Jul 2019
http://sigmod2019.org/

Conference

ConferenceACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019)
Abbreviated titleSIGMOD 2019
CountryNetherlands
CityAmsterdam
Period30/06/195/07/19
Internet address

Abstract

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 the following: can we 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 piecewise 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 the undecidability of reasoning. We finally study the relative expressiveness of the query languages based on (piece-wise linear) warded sets of TGDs.

    Research areas

  • reasoning, query answering, Datalog, tuple-generating dependencies, complexity, expressive power

Event

ACM SIGMOD/PODS International Conference on Management of Data (SIGMOD 2019)

30/06/195/07/19

Amsterdam, Netherlands

Event: Conference

ID: 84254582