On the Relationship between Shy and Warded Datalog+/-
- URL: http://arxiv.org/abs/2202.06285v1
- Date: Sun, 13 Feb 2022 11:24:22 GMT
- Title: On the Relationship between Shy and Warded Datalog+/-
- Authors: Teodoro Baldazzi, Luigi Bellomarini, Marco Favorito, Emanuel Sallinger
- Abstract summary: DatalogE is the extension of Datalog with existential quantification.
It is suitable for modern applications on knowledge graphs, query answering (QA) over such language is known to be undecidable in general.
Different fragments have emerged, introducing syntactic limitations to DatalogE that strike a balance between its expressive power and the computational complexity of QA.
- Score: 3.4696964555947694
- License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
- Abstract: Datalog^E is the extension of Datalog with existential quantification. While
its high expressive power, underpinned by a simple syntax and the support for
full recursion, renders it particularly suitable for modern applications on
knowledge graphs, query answering (QA) over such language is known to be
undecidable in general. For this reason, different fragments have emerged,
introducing syntactic limitations to Datalog^E that strike a balance between
its expressive power and the computational complexity of QA, to achieve
decidability. In this short paper, we focus on two promising tractable
candidates, namely Shy and Warded Datalog+/-. Reacting to an explicit interest
from the community, we shed light on the relationship between these fragments.
Moreover, we carry out an experimental analysis of the systems implementing Shy
and Warded, respectively DLV^E and Vadalog.
Related papers
- Integrating Large Language Models with Graph-based Reasoning for Conversational Question Answering [58.17090503446995]
We focus on a conversational question answering task which combines the challenges of understanding questions in context and reasoning over evidence gathered from heterogeneous sources like text, knowledge graphs, tables, and infoboxes.
Our method utilizes a graph structured representation to aggregate information about a question and its context.
arXiv Detail & Related papers (2024-06-14T13:28:03Z) - Optimizing Language Model's Reasoning Abilities with Weak Supervision [48.60598455782159]
We present textscPuzzleBen, a weakly supervised benchmark that comprises 25,147 complex questions, answers, and human-generated rationales.
A unique aspect of our dataset is the inclusion of 10,000 unannotated questions, enabling us to explore utilizing fewer supersized data to boost LLMs' inference capabilities.
arXiv Detail & Related papers (2024-05-07T07:39:15Z) - Ontological Reasoning over Shy and Warded Datalog$+/-$ for
Streaming-based Architectures (technical report) [6.689509223124273]
Datalog-based ontological reasoning systems adopt languages, often shared under the collective name of Datalog$ +/-$.
In this paper, we focus on two extremely promising, expressive, and tractable languages, namely, Shy and Warded Datalog$ +/-$.
We leverage their theoretical underpinnings to introduce novel reasoning techniques, technically, "chase variants", that are particularly fit for efficient reasoning in streaming-based architectures.
We then implement them in Vadalog, our reference streaming-based engine, to efficiently solve ontological reasoning tasks over real-world settings.
arXiv Detail & Related papers (2023-11-20T23:27:43Z) - Log Parsing Evaluation in the Era of Modern Software Systems [47.370291246632114]
We focus on one integral part of automated log analysis, log parsing, which is the prerequisite to deriving any insights from logs.
Our investigation reveals problematic aspects within the log parsing field, particularly its inefficiency in handling heterogeneous real-world logs.
We propose a tool, Logchimera, that enables estimating log parsing performance in industry contexts.
arXiv Detail & Related papers (2023-08-17T14:19:22Z) - Modeling Hierarchical Reasoning Chains by Linking Discourse Units and
Key Phrases for Reading Comprehension [80.99865844249106]
We propose a holistic graph network (HGN) which deals with context at both discourse level and word level, as the basis for logical reasoning.
Specifically, node-level and type-level relations, which can be interpreted as bridges in the reasoning process, are modeled by a hierarchical interaction mechanism.
arXiv Detail & Related papers (2023-06-21T07:34:27Z) - ConvFinQA: Exploring the Chain of Numerical Reasoning in Conversational
Finance Question Answering [70.6359636116848]
We propose a new large-scale dataset, ConvFinQA, to study the chain of numerical reasoning in conversational question answering.
Our dataset poses great challenge in modeling long-range, complex numerical reasoning paths in real-world conversations.
arXiv Detail & Related papers (2022-10-07T23:48:50Z) - Complexity of Arithmetic in Warded Datalog+- [1.5469452301122173]
Warded Datalog+- extends the logic-based language Datalog with existential quantifiers in rule heads.
We define a new language that extends Warded Datalog+- with arithmetic and prove its P-completeness.
We present an efficient reasoning algorithm for our newly defined language and prove descriptive complexity for a recently introduced Datalog fragment with integer arithmetic.
arXiv Detail & Related papers (2022-02-10T15:14:03Z) - 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) - Competency Problems: On Finding and Removing Artifacts in Language Data [50.09608320112584]
We argue that for complex language understanding tasks, all simple feature correlations are spurious.
We theoretically analyze the difficulty of creating data for competency problems when human bias is taken into account.
arXiv Detail & Related papers (2021-04-17T21:34:10Z) - iWarded: A System for Benchmarking Datalog+/- Reasoning (technical
report) [0.0]
iWarded is a system that can generate very large, complex, realistic reasoning settings.
We present the iWarded system and a set of novel theoretical results adopted to generate effective scenarios.
arXiv Detail & Related papers (2021-03-15T17:56:46Z) - A tetrachotomy of ontology-mediated queries with a covering axiom [1.749935196721634]
Our concern is the problem of efficiently determining the data complexity of answering queries mediated by description and their optimal rewritings to standard database queries.
We focus on Boolean conjunctive-mediated queries called disjunctive sirups (or d-sirups)
Some d-sirups only have exponential-size resolution features, some only double-exponential-size positive existential existential-rewritings and single-exprecursive datalog rewritings.
arXiv Detail & Related papers (2020-06-07T14:47:07Z)
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.