Efficient processing of probabilistic set-containment queries on uncertain set-valued data

详细信息	查看全文 | 推荐本文 |

• 作者：Xiaolong Zhang^a ; ^{xiaolongzhang@zju.edu.cn} ; Ke Chen^a ; ^{chenk@zju.edu.cn} ; Lidan Shou^a ; ^{should@zju.edu.cn} ; Gang Chen^a ; ^{cg@zju.edu.cn} ; Yuan Gao^a ; ^{yuangao1@zju.edu.cn} ; Kian-Lee Tan^b ; ^{tankl@comp.nus.edu.sg}
• 关键词：Probabilistic set-containment query/join ; Uncertain set-valued attributes ; Uncertain set-valued data ; Uncertain query ; Set containment query ; Expected Jaccard containment
• 刊名：Information Sciences
• 出版年：2012
• 期刊代码：62_00200255
• 类别：cp
• 出版时间：1 August, 2012
• 卷：196
• 期：Complete
• 页码：97-117
• 文件大小：912 K

摘要

Set-valued data is a natural and concise representation for modeling complex objects. As an important operation of object-oriented or object-relational database, set containment query processing over set-valued data has been extensively studied in previous works. Recently, there is a growing realization that uncertain information is a first-class citizen in modern database management. As such, there is a strong demand for study of set containment queries over uncertain set-valued data.

This paper investigates how set-containment queries over uncertain set-valued data can be efficiently processed. Based on the popular possible world semantics, we first present a practical model in which the uncertainty in set-valued data is represented by existential probabilities, and propose the probabilistic set containment semantics and its generalization - the expected Jaccard containment. Second, to avoid expensive computations in enumerating all possible worlds, we develop efficient schemes for computing these two probabilistic semantics. Third, we introduce two important queries, namely probability threshold containment query (PTCQ) and probability threshold containment join (PTCJ), and propose novel techniques to process them efficiently. Finally, we conduct extensive experiments to study the efficiency of the proposed methods. The experimental results indicate that the proposed methods are efficient in processing the uncertain set containment queries.