In:
ACM Transactions on Database Systems, Association for Computing Machinery (ACM), Vol. 45, No. 2 ( 2020-06-30), p. 1-47
Abstract:
Numeric inconsistencies are common in real-life knowledge bases and social networks. To catch such errors, we extend graph functional dependencies with linear arithmetic expressions and built-in comparison predicates, referred to as numeric graph dependencies (NGDs). We study fundamental problems for NGDs. We show that their satisfiability, implication, and validation problems are Σ p 2 -complete, Π p 2 -complete, and coNP-complete, respectively. However, if we allow non-linear arithmetic expressions, even of degree at most 2, the satisfiability and implication problems become undecidable. In other words, NGDs strike a balance between expressivity and complexity. To make practical use of NGDs, we develop an incremental algorithm IncDect to detect errors in a graph G using NGDs in response to updates Δ G to G . We show that the incremental validation problem is coNP-complete. Nonetheless, algorithm IncDect is localizable, i.e., its cost is determined by small neighbors of nodes in Δ G instead of the entire G . Moreover, we parallelize IncDect such that it guarantees to reduce running time with the increase of processors. In addition, to strike a balance between the efficiency and accuracy, we also develop polynomial-time parallel algorithms for detection and incremental detection of top-ranked inconsistencies. Using real-life and synthetic graphs, we experimentally verify the scalability and efficiency of the algorithms.
Type of Medium:
Online Resource
ISSN:
0362-5915
,
1557-4644
Language:
English
Publisher:
Association for Computing Machinery (ACM)
Publication Date:
2020
detail.hit.zdb_id:
196155-X
detail.hit.zdb_id:
2006335-0
Permalink
