Traditional high-utility itemsets mining (HUIM) incorporates the concept of utility (e.g., profit) over certain databases. However, an item or itemset is not only present or absent in the transactions but also associated with an existing probability especially the data is collected from the sensor environment. The topic of HUIM from uncertain databases has not yet been addressed though it is commonly seen in real-world applications. In this paper, we propose a novel framework for mining potential high-utility itemsets (PHUIs) over uncertain databases. The upper-bound-based PHUI-UP algorithm is firstly presented to level-wisely mine PHUIs. Based on the probability-utility (PU)-list structure, an improved (PHUI-List) algorithm is further developed to mine PHUIs directly without candidate generation. Substantial experiments are conducted on both real-life and synthetic datasets to show the performance of two designed algorithms in terms of runtime, number of patterns, and scalability.