An epistemic approach to model uncertainty in data-graphs

DOI10.1016/J.IJAR.2023.108948arXiv2109.14112MaRDI QIDQ6137843FDOQ6137843

Authors: Sergio Abriola, Maria Vanina Martinez, Nina Pardal, Edwin Pin 

Publication date: 4 September 2023

Published in: International Journal of Approximate Reasoning (Search for Journal in Brave)

Abstract: Graph databases are becoming widely successful as data models that allow to effectively represent and process complex relationships among various types of data. As with any other type of data repository, graph databases may suffer from errors and discrepancies with respect to the real-world data they intend to represent. In this work we explore the notion of probabilistic unclean graph databases, previously proposed for relational databases, in order to capture the idea that the observed (unclean) graph database is actually the noisy version of a clean one that correctly models the world but that we know partially. As the factors that may be involved in the observation can be many, e.g, all different types of clerical errors or unintended transformations of the data, we assume a probabilistic model that describes the distribution over all possible ways in which the clean (uncertain) database could have been polluted. Based on this model we define two computational problems: data cleaning and probabilistic query answering and study for both of them their corresponding complexity when considering that the transformation of the database can be caused by either removing (subset) or adding (superset) nodes and edges.

Full work available at URL: https://arxiv.org/abs/2109.14112

zbMATH Keywords

constraintsinconsistent databasesconsistent query answeringrepairingdata-graphsprobabilistic query answering

Mathematics Subject Classification ID

Reasoning under uncertainty in the context of artificial intelligence (68T37)

Cites Work

• Title not available (Why is that?)
• Minimal-change integrity maintenance using tuple deletions
• On the data complexity of consistent query answering
• Regular path queries with constraints
• Query processing on probabilistic data: a survey
• An indexing framework for queries on probabilistic graphs
• Path constraints in semistructured databases
• The dichotomy of probabilistic inference for unions of conjunctive queries
• Combined tractability of query evaluation via tree automata and cycluits
• Exact model counting of query expressions. Limitations of propositional methods
• On the data complexity of consistent query answering over graph databases
• Querying Graphs with Data
• An abductive framework for Datalog\(^\pm\) ontologies
• Verification of evolving graph-structured data under expressive path constraints
• Title not available (Why is that?)
• The Complexity of Counting Problems Over Incomplete Databases
• Title not available (Why is that?)

Cited In (2)

• Uncertain Graph Processing through Representative Instances
• Data graphs with incomplete information (and a way to complete them)

This page was built for publication: An epistemic approach to model uncertainty in data-graphs

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q6137843)