%0 Journal Article %1 Dalvi2007Efficient %A Dalvi, Nilesh %A Suciu, Dan %D 2007 %J The VLDB Journal The International Journal on Very Large Data Bases %K db dbir ir phd query schema_matching uncertainty %N 4 %P 523--544 %R http://dx.doi.org/10.1007/s00778-006-0004-3 %T Efficient query evaluation on probabilistic databases %U http://dx.doi.org/10.1007/s00778-006-0004-3 %V 16 %X Abstract  We describe a framework for supporting arbitrarily complex SQL queries with “uncertain” predicates. The query semantics is based on a probabilistic model and the results are ranked, much like in Information Retrieval. Our main focus is query evaluation. We describe an optimization algorithm that can compute efficiently most queries. We show, however, that the data complexity of some queries is \#P-complete, which implies that these queries do not admit any efficient evaluation methods. For these queries we describe both an approximation algorithm and a Monte-Carlo simulation algorithm.

@article{Dalvi2007Efficient, abstract = {Abstract\ \ We describe a framework for supporting arbitrarily complex SQL queries with “uncertain” predicates. The query semantics is based on a probabilistic model and the results are ranked, much like in Information Retrieval. Our main focus is query evaluation. We describe an optimization algorithm that can compute efficiently most queries. We show, however, that the data complexity of some queries is \#P-complete, which implies that these queries do not admit any efficient evaluation methods. For these queries we describe both an approximation algorithm and a Monte-Carlo simulation algorithm.}, added-at = {2009-03-12T15:42:50.000+0100}, author = {Dalvi, Nilesh and Suciu, Dan}, biburl = {https://www.bibsonomy.org/bibtex/2287747c3f72875ec2757b8d404ad6087/lillejul}, citeulike-article-id = {1707736}, doi = {http://dx.doi.org/10.1007/s00778-006-0004-3}, interhash = {e4f79d83de30ea362e24f8b83a301197}, intrahash = {287747c3f72875ec2757b8d404ad6087}, journal = {The VLDB Journal The International Journal on Very Large Data Bases}, keywords = {db dbir ir phd query schema_matching uncertainty}, month = {October}, number = 4, pages = {523--544}, posted-at = {2007-09-29 11:29:10}, priority = {3}, timestamp = {2009-03-13T11:34:05.000+0100}, title = {Efficient query evaluation on probabilistic databases}, url = {http://dx.doi.org/10.1007/s00778-006-0004-3}, volume = 16, year = 2007 }