A Differential Datalog Interpreter
The core reasoning task for datalog engines is materialization, the evaluation of a datalog program over a database alongside its physical incorporation into the database itself. The de-facto method of computing is through the recursive application of inference rules. Due to it being a costly operat...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
MDPI AG
2023-09-01
|
| Series: | Software |
| Subjects: | |
| Online Access: | https://www.mdpi.com/2674-113X/2/3/20 |
| _version_ | 1797576848602824704 |
|---|---|
| author | Matthew James Stephenson |
| author_facet | Matthew James Stephenson |
| author_sort | Matthew James Stephenson |
| collection | DOAJ |
| description | The core reasoning task for datalog engines is materialization, the evaluation of a datalog program over a database alongside its physical incorporation into the database itself. The de-facto method of computing is through the recursive application of inference rules. Due to it being a costly operation, it is a must for datalog engines to provide incremental materialization; that is, to adjust the computation to new data instead of restarting from scratch. One of the major caveats is that deleting data is notoriously more involved than adding since one has to take into account all possible data that has been entailed from what is being deleted. Differential dataflow is a computational model that provides efficient incremental maintenance, notoriously with equal performance between additions and deletions, and work distribution of iterative dataflows. In this paper, we investigate the performance of materialization with three reference datalog implementations, out of which one is built on top of a lightweight relational engine, and the two others are differential-dataflow and non-differential versions of the same rewrite algorithm with the same optimizations. Experimental results suggest that monotonic aggregation is more powerful than ascenting merely the powerset lattice. |
| first_indexed | 2024-03-10T21:59:33Z |
| format | Article |
| id | doaj.art-96cf60ca5d80485b8e7509766f65e1ab |
| institution | Directory Open Access Journal |
| issn | 2674-113X |
| language | English |
| last_indexed | 2024-03-10T21:59:33Z |
| publishDate | 2023-09-01 |
| publisher | MDPI AG |
| record_format | Article |
| series | Software |
| spelling | doaj.art-96cf60ca5d80485b8e7509766f65e1ab2023-11-19T12:59:41ZengMDPI AGSoftware2674-113X2023-09-012342744610.3390/software2030020A Differential Datalog InterpreterMatthew James Stephenson0Computer Science Department, Stanford University, Stanford, CA 94305-9045, USAThe core reasoning task for datalog engines is materialization, the evaluation of a datalog program over a database alongside its physical incorporation into the database itself. The de-facto method of computing is through the recursive application of inference rules. Due to it being a costly operation, it is a must for datalog engines to provide incremental materialization; that is, to adjust the computation to new data instead of restarting from scratch. One of the major caveats is that deleting data is notoriously more involved than adding since one has to take into account all possible data that has been entailed from what is being deleted. Differential dataflow is a computational model that provides efficient incremental maintenance, notoriously with equal performance between additions and deletions, and work distribution of iterative dataflows. In this paper, we investigate the performance of materialization with three reference datalog implementations, out of which one is built on top of a lightweight relational engine, and the two others are differential-dataflow and non-differential versions of the same rewrite algorithm with the same optimizations. Experimental results suggest that monotonic aggregation is more powerful than ascenting merely the powerset lattice.https://www.mdpi.com/2674-113X/2/3/20datalogincremental view maintenancedifferential dataflow |
| spellingShingle | Matthew James Stephenson A Differential Datalog Interpreter Software datalog incremental view maintenance differential dataflow |
| title | A Differential Datalog Interpreter |
| title_full | A Differential Datalog Interpreter |
| title_fullStr | A Differential Datalog Interpreter |
| title_full_unstemmed | A Differential Datalog Interpreter |
| title_short | A Differential Datalog Interpreter |
| title_sort | differential datalog interpreter |
| topic | datalog incremental view maintenance differential dataflow |
| url | https://www.mdpi.com/2674-113X/2/3/20 |
| work_keys_str_mv | AT matthewjamesstephenson adifferentialdataloginterpreter AT matthewjamesstephenson differentialdataloginterpreter |