Tracing errors in probabilistic databases based on the Bayesian network

Liang Duan; Kun Yue; Cheqing Jin; Wenlin Xu; Weiyi Liu

doi:10.1007/978-3-319-18123-3_7

Tracing errors in probabilistic databases based on the Bayesian network

Liang Duan
, Kun Yue^*
, Cheqing Jin
, Wenlin Xu
, Weiyi Liu

^*Corresponding author for this work

School of Data Science and Engineering

Yunnan University

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

3 Scopus citations

Abstract

Data in probabilistic databases may not be absolutely correct, and worse, may be erroneous. Many existing data cleaning methods can be used to detect errors in traditional databases, but they fall short of guiding us to find errors in probabilistic databases, especially for databases with complex correlations among data. In this paper, we propose a method for tracing errors in probabilistic databases by adopting Bayesian network (BN) as the framework of representing the correlations among data. We first develop the techniques to construct an augmented Bayesian network (ABN) for an anomalous query to represent correlations among input data, intermediate data and output data in the query execution. Inspired by the notion of blame in causal models, we then define a notion of blame for ranking candidate errors. Next, we provide an efficient method for computing the degree of blame for each candidate error based on the probabilistic inference upon the ABN. Experimental results show the effectiveness and efficiency of our method.

Original language	English
Title of host publication	Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II
Editors	Muhammad Aamir Cheema, Matthias Renz, Cyrus Shahabi, Xiaofang Zhou
Publisher	Springer Verlag
Pages	104-119
Number of pages	16
ISBN (Print)	9783319181226
DOIs	https://doi.org/10.1007/978-3-319-18123-3_7
State	Published - 2015
Event	20th International Conference on Database Systems for Advanced Applications, DASFAA 2015 - Hanoi, Viet Nam Duration: 20 Apr 2015 → 23 Apr 2015

Publication series

Name	Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)
Volume	9050
ISSN (Print)	0302-9743
ISSN (Electronic)	1611-3349

Conference

Conference	20th International Conference on Database Systems for Advanced Applications, DASFAA 2015
Country/Territory	Viet Nam
City	Hanoi
Period	20/04/15 → 23/04/15

Keywords

Bayesian network
Data cleaning
Probabilistic database
Probabilistic inference
Rejection sampling

Access to Document

10.1007/978-3-319-18123-3_7

Cite this

Duan, L., Yue, K., Jin, C., Xu, W., & Liu, W. (2015). Tracing errors in probabilistic databases based on the Bayesian network. In M. A. Cheema, M. Renz, C. Shahabi, & X. Zhou (Eds.), Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II (pp. 104-119). (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9050). Springer Verlag. https://doi.org/10.1007/978-3-319-18123-3_7

Duan, Liang ; Yue, Kun ; Jin, Cheqing et al. / Tracing errors in probabilistic databases based on the Bayesian network. Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II. editor / Muhammad Aamir Cheema ; Matthias Renz ; Cyrus Shahabi ; Xiaofang Zhou. Springer Verlag, 2015. pp. 104-119 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)).

@inproceedings{b76f7a84ff1245bab7f34b1fbf2b57c6,

title = "Tracing errors in probabilistic databases based on the Bayesian network",

abstract = "Data in probabilistic databases may not be absolutely correct, and worse, may be erroneous. Many existing data cleaning methods can be used to detect errors in traditional databases, but they fall short of guiding us to find errors in probabilistic databases, especially for databases with complex correlations among data. In this paper, we propose a method for tracing errors in probabilistic databases by adopting Bayesian network (BN) as the framework of representing the correlations among data. We first develop the techniques to construct an augmented Bayesian network (ABN) for an anomalous query to represent correlations among input data, intermediate data and output data in the query execution. Inspired by the notion of blame in causal models, we then define a notion of blame for ranking candidate errors. Next, we provide an efficient method for computing the degree of blame for each candidate error based on the probabilistic inference upon the ABN. Experimental results show the effectiveness and efficiency of our method.",

keywords = "Bayesian network, Data cleaning, Probabilistic database, Probabilistic inference, Rejection sampling",

author = "Liang Duan and Kun Yue and Cheqing Jin and Wenlin Xu and Weiyi Liu",

note = "Publisher Copyright: {\textcopyright} 2015, Springer International Publishing Switzerland, All rights Reserved.; 20th International Conference on Database Systems for Advanced Applications, DASFAA 2015 ; Conference date: 20-04-2015 Through 23-04-2015",

year = "2015",

doi = "10.1007/978-3-319-18123-3\_7",

language = "英语",

isbn = "9783319181226",

series = "Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)",

publisher = "Springer Verlag",

pages = "104--119",

editor = "Cheema, \{Muhammad Aamir\} and Matthias Renz and Cyrus Shahabi and Xiaofang Zhou",

booktitle = "Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II",

address = "德国",

}

Duan, L, Yue, K, Jin, C, Xu, W & Liu, W 2015, Tracing errors in probabilistic databases based on the Bayesian network. in MA Cheema, M Renz, C Shahabi & X Zhou (eds), Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II. Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics), vol. 9050, Springer Verlag, pp. 104-119, 20th International Conference on Database Systems for Advanced Applications, DASFAA 2015, Hanoi, Viet Nam, 20/04/15. https://doi.org/10.1007/978-3-319-18123-3_7

Tracing errors in probabilistic databases based on the Bayesian network. / Duan, Liang; Yue, Kun; Jin, Cheqing et al.
Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II. ed. / Muhammad Aamir Cheema; Matthias Renz; Cyrus Shahabi; Xiaofang Zhou. Springer Verlag, 2015. p. 104-119 (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics); Vol. 9050).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - Tracing errors in probabilistic databases based on the Bayesian network

AU - Duan, Liang

AU - Yue, Kun

AU - Jin, Cheqing

AU - Xu, Wenlin

AU - Liu, Weiyi

PY - 2015

Y1 - 2015

N2 - Data in probabilistic databases may not be absolutely correct, and worse, may be erroneous. Many existing data cleaning methods can be used to detect errors in traditional databases, but they fall short of guiding us to find errors in probabilistic databases, especially for databases with complex correlations among data. In this paper, we propose a method for tracing errors in probabilistic databases by adopting Bayesian network (BN) as the framework of representing the correlations among data. We first develop the techniques to construct an augmented Bayesian network (ABN) for an anomalous query to represent correlations among input data, intermediate data and output data in the query execution. Inspired by the notion of blame in causal models, we then define a notion of blame for ranking candidate errors. Next, we provide an efficient method for computing the degree of blame for each candidate error based on the probabilistic inference upon the ABN. Experimental results show the effectiveness and efficiency of our method.

AB - Data in probabilistic databases may not be absolutely correct, and worse, may be erroneous. Many existing data cleaning methods can be used to detect errors in traditional databases, but they fall short of guiding us to find errors in probabilistic databases, especially for databases with complex correlations among data. In this paper, we propose a method for tracing errors in probabilistic databases by adopting Bayesian network (BN) as the framework of representing the correlations among data. We first develop the techniques to construct an augmented Bayesian network (ABN) for an anomalous query to represent correlations among input data, intermediate data and output data in the query execution. Inspired by the notion of blame in causal models, we then define a notion of blame for ranking candidate errors. Next, we provide an efficient method for computing the degree of blame for each candidate error based on the probabilistic inference upon the ABN. Experimental results show the effectiveness and efficiency of our method.

KW - Bayesian network

KW - Data cleaning

KW - Probabilistic database

KW - Probabilistic inference

KW - Rejection sampling

UR - https://www.scopus.com/pages/publications/84942693265

U2 - 10.1007/978-3-319-18123-3_7

DO - 10.1007/978-3-319-18123-3_7

M3 - 会议稿件

AN - SCOPUS:84942693265

SN - 9783319181226

T3 - Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

SP - 104

EP - 119

BT - Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II

A2 - Cheema, Muhammad Aamir

A2 - Renz, Matthias

A2 - Shahabi, Cyrus

A2 - Zhou, Xiaofang

PB - Springer Verlag

T2 - 20th International Conference on Database Systems for Advanced Applications, DASFAA 2015

Y2 - 20 April 2015 through 23 April 2015

ER -

Duan L, Yue K, Jin C, Xu W, Liu W. Tracing errors in probabilistic databases based on the Bayesian network. In Cheema MA, Renz M, Shahabi C, Zhou X, editors, Database Systems for Advanced Applications - 20th International Conference, DASFAA 2015, Hanoi, Vietnam, April 20-23, 2015 Proceedings, Part II. Springer Verlag. 2015. p. 104-119. (Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)). doi: 10.1007/978-3-319-18123-3_7

Tracing errors in probabilistic databases based on the Bayesian network

Abstract

Publication series

Conference

Keywords

Access to Document

Other files and links

Fingerprint

Cite this