Computational Complexity of Preferred Subset Repairs on Data-Graphs

• URL: http://arxiv.org/abs/2402.09265v2
• Date: Mon, 27 May 2024 15:24:32 GMT
• Title: Computational Complexity of Preferred Subset Repairs on Data-Graphs
• Authors: Nina Pardal, Santiago Cifuentes, Edwin Pin, Maria Vanina Martinez, Sergio Abriola,
• Abstract summary: We study the problem of computing prioritized repairs over graph databases with data values. We present several preference criteria based on the standard subset repair semantics. We show that it is possible to maintain the same computational complexity as in the case where no preference criterion is available for exploitation.
• Score: 2.254434034390529
• License: http://arxiv.org/licenses/nonexclusive-distrib/1.0/
• Abstract: Preferences are a pivotal component in practical reasoning, especially in tasks that involve decision-making over different options or courses of action that could be pursued. In this work, we focus on repairing and querying inconsistent knowledge bases in the form of graph databases, which involves finding a way to solve conflicts in the knowledge base and considering answers that are entailed from every possible repair, respectively. Without a priori domain knowledge, all possible repairs are equally preferred. Though that may be adequate for some settings, it seems reasonable to establish and exploit some form of preference order among the potential repairs. We study the problem of computing prioritized repairs over graph databases with data values, using a notion of consistency based on GXPath expressions as integrity constraints. We present several preference criteria based on the standard subset repair semantics, incorporating weights, multisets, and set-based priority levels. We show that it is possible to maintain the same computational complexity as in the case where no preference criterion is available for exploitation. Finally, we explore the complexity of consistent query answering in this setting and obtain tight lower and upper bounds for all the preference criteria introduced.

Related papers

• Optimal Baseline Corrections for Off-Policy Contextual Bandits [61.740094604552475]
  We aim to learn decision policies that optimize an unbiased offline estimate of an online reward metric. We propose a single framework built on their equivalence in learning scenarios. Our framework enables us to characterize the variance-optimal unbiased estimator and provide a closed-form solution for it.
  arXiv  Detail & Related papers  (2024-05-09T12:52:22Z)
• Adaptive-RAG: Learning to Adapt Retrieval-Augmented Large Language Models through Question Complexity [59.57065228857247]
  Retrieval-augmented Large Language Models (LLMs) have emerged as a promising approach to enhancing response accuracy in several tasks, such as Question-Answering (QA) We propose a novel adaptive QA framework, that can dynamically select the most suitable strategy for (retrieval-augmented) LLMs based on the query complexity. We validate our model on a set of open-domain QA datasets, covering multiple query complexities, and show that ours enhances the overall efficiency and accuracy of QA systems.
  arXiv  Detail & Related papers  (2024-03-21T13:52:30Z)
• Consistent Query Answering for Existential Rules with Closed Predicates [2.559168320734115]
  Consistent Query Answering (CQA) is an inconsistency-tolerant approach to data access in databases. We study CQA in databases with data dependencies expressed by existential rules.
  arXiv  Detail & Related papers  (2024-01-11T08:48:40Z)
• $\text{EFO}_{k}$-CQA: Towards Knowledge Graph Complex Query Answering beyond Set Operation [36.77373013615789]
  We propose a framework for data generation, model training, and method evaluation. We construct a dataset, $textEFO_k$-CQA, with 741 types of query for empirical evaluation.
  arXiv  Detail & Related papers  (2023-07-15T13:18:20Z)
• Inconsistency Handling in Prioritized Databases with Universal Constraints: Complexity Analysis and Links with Active Integrity Constraints [5.87010466783654]
  This paper revisits the problem of repairing and querying inconsistent databases equipped with universal constraints. We adopt symmetric difference repairs, in which both deletions and additions of facts can be used to restore consistency. We show how existing notions of optimal repairs, defined for simpler denial constraints and repairs solely based on fact deletion, can be suitably extended to our richer setting.
  arXiv  Detail & Related papers  (2023-06-06T09:17:56Z)
• Conjunctive Query Based Constraint Solving For Feature Model Configuration [79.14348940034351]
  We show how to apply conjunctive queries to solve constraint satisfaction problems. This approach allows the application of a wide-spread database technology to solve configuration tasks.
  arXiv  Detail & Related papers  (2023-04-26T10:08:07Z)
• On the complexity of finding set repairs for data-graphs [2.519906683279153]
  We study the problem of computing a subset and superset repairs for graph databases with data values. We show that for positive fragments of Reg-GX expressions these problems admit a subset-time algorithm, while the full expressive power of the language renders them intractable.
  arXiv  Detail & Related papers  (2022-06-15T13:01:26Z)
• CoreDiag: Eliminating Redundancy in Constraint Sets [68.8204255655161]
  We present a new algorithm which can be exploited for the determination of minimal cores (minimal non-redundant constraint sets) The algorithm is especially useful for distributed knowledge engineering scenarios where the degree of redundancy can become high. In order to show the applicability of our approach, we present an empirical study conducted with commercial configuration knowledge bases.
  arXiv  Detail & Related papers  (2021-02-24T09:16:10Z)
• An Efficient Diagnosis Algorithm for Inconsistent Constraint Sets [68.8204255655161]
  We introduce a divide-and-conquer based diagnosis algorithm (FastDiag) which identifies minimal sets of faulty constraints in an over-constrained problem. We compare FastDiag with the conflict-directed calculation of hitting sets and present an in-depth performance analysis.
  arXiv  Detail & Related papers  (2021-02-17T19:55:42Z)
• Robust Question Answering Through Sub-part Alignment [53.94003466761305]
  We model question answering as an alignment problem. We train our model on SQuAD v1.1 and test it on several adversarial and out-of-domain datasets.
  arXiv  Detail & Related papers  (2020-04-30T09:10:57Z)
• Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation [5.87010466783654]
  We study the issue of inconsistency over prioritized knowledge bases (KBs) We propose a novel semantics for prioritized KBs inspired by grounded extensions and enjoys favourable properties. Our study also yields some results of independent interest concerning preference-based argumentation frameworks.
  arXiv  Detail & Related papers  (2020-03-12T12:38:37Z)

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.