Aggregate Queries On Constrained Probabilistic Similarity Join Pairs

Join aggregate queries are very common in database processing,on-line analytical processing(OLAP),and data warehouse.These queries often combine multiple tables into a single one,and then summarize it with aggregate functions.However,with the emergence of uncertain data in databases and data warehouses,join aggregate queries often face with failure during the join phase.Probabilistic Similarity Join(PSJ),which is based on probabilistic similarity functions,can solve join problems on uncertain data effectively.However,aggregate queries on PSJ pairs are facing challenges.On the one hand,traditional aggregate methods are not applicable to such aggregate queries because of the complex mapping constraints of PSJ.On the other hand,existing methods only support aggregate queries on PSJ pairs with one-to-one mapping constraint,and they are not efficient enough.We aim to solve the problems of aggregate queries on all types of constrained PSJ pairs.First,for PSJ pairs with many-to-many mapping constraint,we model them with a tuple-level uncertainty model,and propose two aggregate methods based on dynamic programming and divide-and-conquer strategy,respectively.Then,we model one-to-many PSJ pairs with an attribute-level uncertainty model,and then extend aggregate algorithms on many-to-many PSJ pairs to this model.Finally,we model one-to-one PSJ pairs with a probabilistic graphical model.By introducing the generating function method,an aggregate method is proposed based on dynamic programming and divide-and-conquer strategy.Extensive experiments on real datasets have demonstrated order-of-magnitude improvements of our methods over baselines.