Many organizations and enterprises use cloud databases to store data to improve management efficiency and save costs. However, cloud service providers may hide the fact that data integrity has been compromised for protecting their business reputation. Thus, how to verify the data integrity of cloud database in an effective way is very important for data owner. Existing integrity verification methods usually require cloud service provider to develop additional interfaces which are hard to be actually deployed. In addition, they cannot effectively detect tampering and deletion of a small amount of data. This paper presents a novel probabilistic integrity verification scheme (called PIV4DB) to address above challenges. Different from traditional methods, PIV4DB efficiently verifies the data integrity of cloud database by randomly selecting part of groups of tuples instead of querying all the tuples. Experimental results demonstrated that with validating 0.5\% among 100k groups, PIV4DB could detect the corruption with 99\% probability when the integrity of 920 out of billions of tuples are compromised. In addition, PIV4DB dose not need extra cooperation with cloud service provider by just adding a new column of random numbers to the database and only using standard SQL statements to verify integrity.