Query Evaluation in DatalogMTL -- Taming Infinite Query Results

• URL: http://arxiv.org/abs/2109.10691v1
• Date: Tue, 21 Sep 2021 09:37:28 GMT
• Title: Query Evaluation in DatalogMTL -- Taming Infinite Query Results
• Authors: Luigi Bellomarini, Markus Nissl and Emanuel Sallinger
• Abstract summary: We study infinite models that eventually become constant and introduce sufficient criteria for programs that allow for such representation. We provide a novel algorithm for reasoning over finite representable DatalogMTL programs that incorporates all of the previously discussed representations.
• Score: 2.9005223064604078
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: In this paper, we investigate finite representations of DatalogMTL. First, we introduce programs that have finite models and propose a toolkit for structuring the execution of DatalogMTL rules into sequential phases. Then, we study infinite models that eventually become constant and introduce sufficient criteria for programs that allow for such representation. We proceed by considering infinite models that are eventually periodic and show that such a representation encompasses all DatalogMTLFP programs, a widely discussed fragment. Finally, we provide a novel algorithm for reasoning over finite representable DatalogMTL programs that incorporates all of the previously discussed representations.

Related papers

• Boolean Matrix Logic Programming [5.847084649531298]
  We describe a datalog query evaluation approach based on efficient and composable matrix modules. We develop two novel BMLP modules for bottom-up manipulation on linear dyadic recursive datalog programs. Our empirical results demonstrate that these modules outperform general-purpose and specialised systems by factors of 30x and 9x, respectively.
  arXiv  Detail & Related papers  (2024-08-19T19:26:49Z)
• Decidable Fragments of LTLf Modulo Theories (Extended Version) [66.25779635347122]
  In general,fMT was shown to be semi-decidable for any decidable first-order theory (e.g., linear arithmetics) with a tableau-based semi-decision procedure. We show that for anyfMT formula satisfies an abstract, semantic condition, that we call finite memory, the tableau augmented with a new rule is also guaranteed to terminate.
  arXiv  Detail & Related papers  (2023-07-31T17:02:23Z)
• Past-present temporal programs over finite traces [1.4835015204811504]
  We study the so-called past-present syntactic subclass, which consists of a set of logic programming rules whose body references to the past and head to the present. We extend the definitions of completion and loop formulas to the case of past-present formulas, which allows capturing the temporal stable models of a set of past-present temporal programs.
  arXiv  Detail & Related papers  (2023-07-24T08:50:12Z)
• MURMUR: Modular Multi-Step Reasoning for Semi-Structured Data-to-Text Generation [102.20036684996248]
  We propose MURMUR, a neuro-symbolic modular approach to text generation from semi-structured data with multi-step reasoning. We conduct experiments on two data-to-text generation tasks like WebNLG and LogicNLG.
  arXiv  Detail & Related papers  (2022-12-16T17:36:23Z)
• Zero-Shot On-the-Fly Event Schema Induction [61.91468909200566]
  We present a new approach in which large language models are utilized to generate source documents that allow predicting, given a high-level event definition, the specific events, arguments, and relations between them. Using our model, complete schemas on any topic can be generated on-the-fly without any manual data collection, i.e., in a zero-shot manner.
  arXiv  Detail & Related papers  (2022-10-12T14:37:00Z)
• Summarization Programs: Interpretable Abstractive Summarization with Neural Modular Trees [89.60269205320431]
  Current abstractive summarization models either suffer from a lack of clear interpretability or provide incomplete rationales. We propose the Summarization Program (SP), an interpretable modular framework consisting of an (ordered) list of binary trees. A Summarization Program contains one root node per summary sentence, and a distinct tree connects each summary sentence to the document sentences.
  arXiv  Detail & Related papers  (2022-09-21T16:50:22Z)
• Seminaive Materialisation in DatalogMTL [10.850687097496373]
  DatalogMTL is an extension of Datalog with metric temporal operators. We propose a materialisation-based procedure to minimise redundant computation. Our experiments show that our optimised seminaive strategy for DatalogMTL is able to significantly reduce materialisation times.
  arXiv  Detail & Related papers  (2022-08-15T10:04:44Z)
• Linear Temporal Logic Modulo Theories over Finite Traces (Extended Version) [72.38188258853155]
  This paper studies Linear Temporal Logic over Finite Traces (LTLf) proposition letters are replaced with first-order formulas interpreted over arbitrary theories. The resulting logic, called Satisfiability Modulo Theories (LTLfMT), is semi-decidable.
  arXiv  Detail & Related papers  (2022-04-28T17:57:33Z)
• MeTeoR: Practical Reasoning in Datalog with Metric Temporal Operators [12.145849273069627]
  We present a novel approach for practical reasoning in DatalogMTL which combines materialisation (a.k.a. forward chaining) with automata-based techniques. MeTeoR is a scalable system which enables reasoning over complex temporal rules and involving datasets of millions of temporal facts.
  arXiv  Detail & Related papers  (2022-01-12T17:46:18Z)
• Self-Supervised Log Parsing [59.04636530383049]
  Large-scale software systems generate massive volumes of semi-structured log records. Existing approaches rely on log-specifics or manual rule extraction. We propose NuLog that utilizes a self-supervised learning model and formulates the parsing task as masked language modeling.
  arXiv  Detail & Related papers  (2020-03-17T19:25:25Z)

This list is automatically generated from the titles and abstracts of the papers in this site.

This site does not guarantee the quality of this site (including all information) and is not responsible for any consequences.