Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation

• URL: http://arxiv.org/abs/2003.05746v3
• Date: Fri, 7 Jun 2024 06:42:55 GMT
• Title: Querying and Repairing Inconsistent Prioritized Knowledge Bases: Complexity Analysis and Links with Abstract Argumentation
• Authors: Meghyn Bienvenu, Camille Bourgaux,
• Abstract summary: 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.
• Score: 5.87010466783654
• License: http://creativecommons.org/licenses/by/4.0/
• Abstract: In this paper, we explore the issue of inconsistency handling over prioritized knowledge bases (KBs), which consist of an ontology, a set of facts, and a priority relation between conflicting facts. In the database setting, a closely related scenario has been studied and led to the definition of three different notions of optimal repairs (global, Pareto, and completion) of a prioritized inconsistent database. After transferring the notions of globally-, Pareto- and completion-optimal repairs to our setting, we study the data complexity of the core reasoning tasks: query entailment under inconsistency-tolerant semantics based upon optimal repairs, existence of a unique optimal repair, and enumeration of all optimal repairs. Our results provide a nearly complete picture of the data complexity of these tasks for ontologies formulated in common DL-Lite dialects. The second contribution of our work is to clarify the relationship between optimal repairs and different notions of extensions for (set-based) argumentation frameworks. Among our results, we show that Pareto-optimal repairs correspond precisely to stable extensions (and often also to preferred extensions), and we propose a novel semantics for prioritized KBs which is inspired by grounded extensions and enjoys favourable computational properties. Our study also yields some results of independent interest concerning preference-based argumentation frameworks.

Related papers

• Computational Complexity of Preferred Subset Repairs on Data-Graphs [2.254434034390529]
  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.
  arXiv  Detail & Related papers  (2024-02-14T15:51:55Z)
• Advancing Counterfactual Inference through Nonlinear Quantile Regression [77.28323341329461]
  We propose a framework for efficient and effective counterfactual inference implemented with neural networks. The proposed approach enhances the capacity to generalize estimated counterfactual outcomes to unseen data. Empirical results conducted on multiple datasets offer compelling support for our theoretical assertions.
  arXiv  Detail & Related papers  (2023-06-09T08:30:51Z)
• 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)
• Rethinking Complex Queries on Knowledge Graphs with Neural Link Predictors [65.56849255423866]
  We propose a new neural-symbolic method to support end-to-end learning using complex queries with provable reasoning capability. We develop a new dataset containing ten new types of queries with features that have never been considered. Our method outperforms previous methods significantly in the new dataset and also surpasses previous methods in the existing dataset at the same time.
  arXiv  Detail & Related papers  (2023-04-14T11:35:35Z)
• Understanding and Constructing Latent Modality Structures in Multi-modal Representation Learning [53.68371566336254]
  We argue that the key to better performance lies in meaningful latent modality structures instead of perfect modality alignment. Specifically, we design 1) a deep feature separation loss for intra-modality regularization; 2) a Brownian-bridge loss for inter-modality regularization; and 3) a geometric consistency loss for both intra- and inter-modality regularization.
  arXiv  Detail & Related papers  (2023-03-10T14:38:49Z)
• Relational Proxies: Emergent Relationships as Fine-Grained Discriminators [52.17542855760418]
  We propose a novel approach that leverages information between the global and local part of an object for encoding its label. We design Proxies based on our theoretical findings and evaluate it on seven challenging fine-grained benchmark datasets. We also experimentally validate our theory and obtain consistent results across multiple benchmarks.
  arXiv  Detail & Related papers  (2022-10-05T11:08:04Z)
• Querying Inconsistent Prioritized Data with ORBITS: Algorithms, Implementation, and Experiments [12.952483242045366]
  We investigate practical algorithms for inconsistency-tolerant query answering over prioritized knowledge bases. We consider three well-known semantics (AR, IAR and brave) based upon two notions of optimal repairs (Pareto and completion)
  arXiv  Detail & Related papers  (2022-02-16T10:44:39Z)
• Multi-task Learning of Order-Consistent Causal Graphs [59.9575145128345]
  We consider the problem of discovering $K related Gaussian acyclic graphs (DAGs) Under multi-task learning setting, we propose a $l_1/l$-regularized maximum likelihood estimator (MLE) for learning $K$ linear structural equation models. We theoretically show that the joint estimator, by leveraging data across related tasks, can achieve a better sample complexity for recovering the causal order.
  arXiv  Detail & Related papers  (2021-11-03T22:10:18Z)
• PRGC: Potential Relation and Global Correspondence Based Joint Relational Triple Extraction [23.998135821388203]
  We propose a joint relational triple extraction framework based on Potential Relation and Global Correspondence (PRGC) PRGC achieves state-of-the-art performance on public benchmarks with higher efficiency and delivers consistent performance gain on complex scenarios of overlapping triples.
  arXiv  Detail & Related papers  (2021-06-18T03:38:07Z)
• Analyzing Semantics of Aggregate Answer Set Programming Using Approximation Fixpoint Theory [1.295566630218982]
  We introduce the notion of a ternary satisfaction relation and define stable semantics in terms of it. We show that ternary satisfaction relations bridge the gap between the standard Gelfond-Lifschitz reduct, and stable semantics as defined in the framework of AFT.
  arXiv  Detail & Related papers  (2021-04-30T07:06:27Z)
• Task-Feature Collaborative Learning with Application to Personalized Attribute Prediction [166.87111665908333]
  We propose a novel multi-task learning method called Task-Feature Collaborative Learning (TFCL) Specifically, we first propose a base model with a heterogeneous block-diagonal structure regularizer to leverage the collaborative grouping of features and tasks. As a practical extension, we extend the base model by allowing overlapping features and differentiating the hard tasks.
  arXiv  Detail & Related papers  (2020-04-29T02:32:04Z)

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.