An epistemic approach to model uncertainty in data-graphs

DOI10.1016/J.IJAR.2023.108948MaRDI QIDQ6137843zbMATH OpenFDO

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)

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)

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.

Cites work

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

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)