In recent years, the concept of data outsourcing has become quite popular. With the appearance of cloud computing, there is a new paradigm: cloud storage. Cloud storage means that the data owner moves its data to a cloud storage server that is supposed to faithfully store the data and make it available to the data owner and perhaps the data requestors. This paper discusses how to guarantee the provable data possession when data dynamics are supported. Different integrity granularities are supported including size integrity, block-number integrity and the block-neighborhood integrity which is realized by rules defined in datalog through neighborhood relationship between data blocks.