Modular materialisation of datalog programs
The seminaïve algorithm can be used to materialise all consequences of a datalog program, and it also forms the basis for algorithms that incrementally update a materialisation as the input facts change. Certain (combinations of) rules, however, can be handled much more efficiently using custom algo...
| Main Authors: | , , |
|---|---|
| Format: | Conference item |
| Published: |
AAAI Press
2019
|
| _version_ | 1826278675112263680 |
|---|---|
| author | Hu, P Motik, B Horrocks, I |
| author_facet | Hu, P Motik, B Horrocks, I |
| author_sort | Hu, P |
| collection | OXFORD |
| description | The seminaïve algorithm can be used to materialise all consequences of a datalog program, and it also forms the basis for algorithms that incrementally update a materialisation as the input facts change. Certain (combinations of) rules, however, can be handled much more efficiently using custom algorithms. To integrate such algorithms into a general reasoning approach that can handle arbitrary rules, we propose a modular framework for computing and maintaining a materialisation. We split a datalog program into modules that can be handled using specialised algorithms, and we handle the remaining rules using the semina¨ıve algorithm. We also present two algorithms for computing the transitive and the symmetric– transitive closure of a relation that can be used within our framework. Finally, we show empirically that our framework can handle arbitrary datalog programs while outperforming existing approaches, often by orders of magnitude. |
| first_indexed | 2024-03-06T23:47:29Z |
| format | Conference item |
| id | oxford-uuid:71713ef7-ae5d-4388-90a8-0ca47251f67b |
| institution | University of Oxford |
| last_indexed | 2024-03-06T23:47:29Z |
| publishDate | 2019 |
| publisher | AAAI Press |
| record_format | dspace |
| spelling | oxford-uuid:71713ef7-ae5d-4388-90a8-0ca47251f67b2022-03-26T19:43:40ZModular materialisation of datalog programsConference itemhttp://purl.org/coar/resource_type/c_5794uuid:71713ef7-ae5d-4388-90a8-0ca47251f67bSymplectic Elements at OxfordAAAI Press2019Hu, PMotik, BHorrocks, IThe seminaïve algorithm can be used to materialise all consequences of a datalog program, and it also forms the basis for algorithms that incrementally update a materialisation as the input facts change. Certain (combinations of) rules, however, can be handled much more efficiently using custom algorithms. To integrate such algorithms into a general reasoning approach that can handle arbitrary rules, we propose a modular framework for computing and maintaining a materialisation. We split a datalog program into modules that can be handled using specialised algorithms, and we handle the remaining rules using the semina¨ıve algorithm. We also present two algorithms for computing the transitive and the symmetric– transitive closure of a relation that can be used within our framework. Finally, we show empirically that our framework can handle arbitrary datalog programs while outperforming existing approaches, often by orders of magnitude. |
| spellingShingle | Hu, P Motik, B Horrocks, I Modular materialisation of datalog programs |
| title | Modular materialisation of datalog programs |
| title_full | Modular materialisation of datalog programs |
| title_fullStr | Modular materialisation of datalog programs |
| title_full_unstemmed | Modular materialisation of datalog programs |
| title_short | Modular materialisation of datalog programs |
| title_sort | modular materialisation of datalog programs |
| work_keys_str_mv | AT hup modularmaterialisationofdatalogprograms AT motikb modularmaterialisationofdatalogprograms AT horrocksi modularmaterialisationofdatalogprograms |