由于在获取、解析数据的过程中存在误差、干扰等因素，很多领域的数据中存在着不确定性，这已成为影响数据性能的重要因素.概率数据库可以存储不确定数据并且返回带有置信度的查询结果.然而，不确定性的累积和传播会降低查询结果的可用性.因此，有必要降低概率数据库中数据的不确定性.致力于解决在概率RDF （Resource Description Framework）数据库图查询中如何由众包来提升查询结果的确定性，基本思想是让众包工作者决定由边表示的关系是否正确，以降低整个查询的不确定性.提出了3种不同的算法来选择使查询结果不确定性下降最大的边.最后，通过实验验证了提出的算法，表明不稳定剪枝算法和稳定剪枝算法具有更好的效果.
Due to the factors such as errors and noises in the process of obtaining and analyzing data, uncertain data arises in many domains, which has emerged as an important issue affecting the performance of data. Uncertain data can be stored in probabilistic databases and query facilities always yield answers with confidence. However, the accumulation and propagation of uncertainty may reduce the usability of the query results. As such, it is desirable to reduce the uncertainty of uncertain data. This paper aims at solving the problem how to promote the answers' certainty in RDF(resource description framework) graph query via crowdsourcing. The basic idea is to ask the crowd to decide whether the relationships represented by some edges are correct. In this paper, we introduce three different algorithms to select the edge which maximizes the uncertainty reduction. Finally, we verify these algorithms by experiments and show that unstable pruning algorithm and stable pruning algorithm perform better in term of efficiency.
[1] DALVI N, SUCIU D. Efficient query evaluation on probabilistic databases[J]. The VLDB Journal-The International Journal on Very Large Data Bases, 2007, 16(4):523-544.
[2] ABITEBOUL S, SENELLART P. Querying and updating probabilistic information in XML[C]//Advances in Database Technology-EDBT 2006, International Conference on Extending Database Technology. DBLP, 2006:1059-1068.
[3] DONG X, GABRILOVICH E, HEITZ G, et al. Knowledge vault:A web-scale approach to probabilistic knowledge fusion[C]//Proceedings of the 20th ACM SIGKDD International Conference on Knowledge Discovery and Data Mining. ACM, 2014:601-610.
[4] ANGLES R, GUTIERREZ C. Querying RDF data from a graph database perspective[C]//European Semantic Web Conference. Berlin:Springer, 2005:346-360.
[5] FANG H, ZHANG X W. pSPARQL:A querying language for probabilistic RDF[C/OL]//Proceedings of the ISWC 2016 Posters & Demonstrations Track Co-Located with 15th International Semantic Web Conference, ISWC 2016.[2016-08-01]. http://ceur-ws.org/Vol-1690/paper18.pdf.
[6] FUKUSHIGE Y. Representing probabilistic relations in RDF[C/OL]//Proceedings of the International Semantic Web Conference, ISWC 2005.[2016-08-01]. http://ceur-ws.org/Vol-173/pospaper5.pdf.
[7] LIAN X, CHEN L. Efficient query answering in probabilistic rdf graphs[C]//Proceedings of the 2011 ACM SIGMOD International Conference on Management of data. ACM, 2011:157-168.
[8] HUANG H, LIU C F. Query evaluation on probabilistic RDF databases[C]//International Conference on Web Information Systems Engineering. Berlin:Springer, 2009:307-320.
[9] UDREA O, SUBRAHMANIAN V S, MAJKIC Z. Probabilistic RDF[C]//Information Reuse and Integration, 2006 IEEE International Conference on. IEEE, 2006:172-177.
[10] ZHANG C J, CHEN L, JAGADISH H V, et al. Reducing uncertainty of schema matching via crowdsourcing[J]. Proceedings of the VLDB Endowment, 2013, 6(9):757-768.
[11] CHENG R, CHEN J C, XIE X K. Cleaning uncertain data with quality guarantees[J]. Proceedings of the VLDB Endowment, 2008(1):722-735.
[12] LEE J, LEE D, HWANG S. CrowdK:Answering top-k queries with crowdsourcing[J]. Information Sciences, 2017, 399:98-120.
[13] CICERI E, FRATERNALI P, MARTINENGHI D, et al. Crowdsourcing for top-k query processing over uncertain data[J]. IEEE Transactions on Knowledge and Data Engineering, 2016, 28(1):41-53.
[14] VERROIOS V, GARCIA-MOLINA H. Entity resolution with crowd errors[C]//2015 IEEE 31st International Conference on Data Engineering. IEEE, 2015:219-230.
[15] ZHANG C J, CHEN L, TONG Y, et al. Cleaning uncertain data with a noisy crowd[C]//2015 IEEE 31st International Conference on Data Engineering. IEEE, 2015:6-17.
[16] MARCUS A, WU E, KARGER D, et al. Human-powered sorts and joins[J]. Proceedings of the VLDB Endowment, 2011, 5(1):13-24.
[17] MARCUS A, WU E, KARGER D R, et al. Crowdsourced databases:Query processing with people[C/OL]//Proceedings of the 5th Biennial Conference on Innovative Data Systems Research, CIDR 2011.[1016-08-01]. http://www-db.cs.wisc.edu/cidr/cidr2011/Papers/CIDR11Paper29.pdf.
[18] SUCHANEK F M, KASNECI G, WEIKUM G. Yago:a core of semantic knowledge[C]//Proceedings of the 16th International Conference on World Wide Web. ACM, 2007:697-706.
中国综合性科技类核心期刊(北大核心)