Abstract: The existing verifiable outsourced database schemes only support some kind of tailored queries with low efficiency and large data expanding rate. Besides, the overheads of verification and update of these schemes are unacceptable. As a result, they cannot be applied into practice. To resolve these problem, we propose a novel primitive called publicly verifiable outsourced database with full operations based on bilinear map. We present a system model and security model of our scheme. Based on bilinear map, we construct a publicly verifiable outsourced database scheme with full operations, and design each algorithm in detail. We present the rigorous security proof under q-BSDH assumption and VBDHE assumption. Finally, we make a comparison with other state of art schemes in two directions: functionality and performance. The theoretical analysis and simulation confirm that our scheme is more functional, efficient and practical. Furthermore, verification and update phases do not require data owner’s private key, and any client owning public key and digest can verify the correctness of query and update database. Therefore, our scheme supports public verification and public update.