Optimised storage for datalog reasoning
Materialisation facilitates Datalog reasoning by precomputing all consequences of the facts and the rules so that queries can be directly answered over the materialised facts. However, storing all materialised facts may be infeasible in practice, especially when the rules are complex and the given s...
| Prif Awduron: | , , , |
|---|---|
| Fformat: | Conference item |
| Iaith: | English |
| Cyhoeddwyd: |
Association for the Advancement of Artificial Intelligence
2024
|
| _version_ | 1826314992884908032 |
|---|---|
| author | Zhang, X Hu, P Nenov, Y Horrocks, I |
| author_facet | Zhang, X Hu, P Nenov, Y Horrocks, I |
| author_sort | Zhang, X |
| collection | OXFORD |
| description | Materialisation facilitates Datalog reasoning by precomputing all consequences of the facts and the rules so that queries can be directly answered over the materialised facts. However, storing all materialised facts may be infeasible in practice, especially when the rules are complex and the given set of facts is large. We observe that for certain combinations of rules, there exist data structures that compactly represent the reasoning result and can be efficiently queried when necessary. In this paper, we present a general framework that allows for the integration of such optimised storage schemes with standard materialisation algorithms. Moreover, we devise optimised storage schemes targeting at transitive rules and union rules, two types of (combination of) rules that commonly occur in practice. Our experimental evaluation shows that our approach significantly improves memory consumption, sometimes by orders of magnitude, while remaining competitive in terms of query answering time. |
| first_indexed | 2024-12-09T03:15:49Z |
| format | Conference item |
| id | oxford-uuid:1c6b73ed-6d8b-4214-bd19-642236f4430c |
| institution | University of Oxford |
| language | English |
| last_indexed | 2024-12-09T03:15:49Z |
| publishDate | 2024 |
| publisher | Association for the Advancement of Artificial Intelligence |
| record_format | dspace |
| spelling | oxford-uuid:1c6b73ed-6d8b-4214-bd19-642236f4430c2024-10-25T09:06:18ZOptimised storage for datalog reasoningConference itemhttp://purl.org/coar/resource_type/c_5794uuid:1c6b73ed-6d8b-4214-bd19-642236f4430cEnglishSymplectic ElementsAssociation for the Advancement of Artificial Intelligence2024Zhang, XHu, PNenov, YHorrocks, IMaterialisation facilitates Datalog reasoning by precomputing all consequences of the facts and the rules so that queries can be directly answered over the materialised facts. However, storing all materialised facts may be infeasible in practice, especially when the rules are complex and the given set of facts is large. We observe that for certain combinations of rules, there exist data structures that compactly represent the reasoning result and can be efficiently queried when necessary. In this paper, we present a general framework that allows for the integration of such optimised storage schemes with standard materialisation algorithms. Moreover, we devise optimised storage schemes targeting at transitive rules and union rules, two types of (combination of) rules that commonly occur in practice. Our experimental evaluation shows that our approach significantly improves memory consumption, sometimes by orders of magnitude, while remaining competitive in terms of query answering time. |
| spellingShingle | Zhang, X Hu, P Nenov, Y Horrocks, I Optimised storage for datalog reasoning |
| title | Optimised storage for datalog reasoning |
| title_full | Optimised storage for datalog reasoning |
| title_fullStr | Optimised storage for datalog reasoning |
| title_full_unstemmed | Optimised storage for datalog reasoning |
| title_short | Optimised storage for datalog reasoning |
| title_sort | optimised storage for datalog reasoning |
| work_keys_str_mv | AT zhangx optimisedstoragefordatalogreasoning AT hup optimisedstoragefordatalogreasoning AT nenovy optimisedstoragefordatalogreasoning AT horrocksi optimisedstoragefordatalogreasoning |