Seminar 29.07.2021

Challenges of Using Leapfrog Triejoin for Datalog Programs

Vortrag von Philipp Hanisch

• Beginn: 29. Juli 2021 um 13:00
• Ende: 29. Juli 2021 um 14:30
• Event series: Research Seminar Logic and AI
• iCal

Datalog is a well-understood relational query language and there are efficient implementations, based on different concepts and technologies. Nevertheless, the search for faster and more efficient reasoners continues. A promising approach for further improvements is the so-called leapfrog triejoin by Veldhuizen. Leapfrog triejoin is a variable-oriented join algorithm and computes the matches of a Datalog rule as a result tree following a previously defined variable order. Leapfrog triejoin is worst-case optimal w.r.t. the AGM bound, which provides a tight bound on the maximum result size of full conjunctive queries, and empirical evaluations suggest that leapfrog triejoin is relevant in practice, too.

The focus of the current research concerning leapfrog triejoin lies on the theoretical and practical aspects of computing a single join. Implementing a Datalog reasoner based on leapfrog triejoin, however, requires to compute the consequences of a Datalog program with several rules and, thus, several joins. The main task is to find variable orders for all the joins that are both locally and globally good. We discuss challenges, which arise naturally in this setting, as well as potential approaches.

This talk will take place online via BigBlueButton. To access the room, take one of the following links:

with ZIH-login:

https://selfservice.zih.tu-dresden.de/l/link.php?m=136288&p=07d4d73e

without ZIH-login:

https://selfservice.zih.tu-dresden.de/link.php?m=136288&p=788f2a1a

• PDF