The study of micro-data disclosure issue has largely focused on the privacy preservation aspect, whereas the integrity of a published micro-data table has received limited attention. Unauthorized updates to such a table may lead users to believe in misleading data. Traditional cryptographic stamp-based approaches allow users to detect unauthorized updates using credentials issued by the data owner. However, to localize the exact corrupted tuples would require a large number of cryptographic stamps to be stored, leading to prohibitive storage requirements. In this thesis, we explore the fact that tuples in a micro-data table must be stored in a particular order, which has no inherent meaning under the relational model. We propose a series of algorithms for embedding watermarks through reordering the tuples. The embedded watermarks allow users to detect, localize, and restore corrupted tuples with a single secret key issued by the data owner, and no additional storage is required. At the same time, our algorithms also allow for efficient updates by the data owner or legitimate users who know the secret key. The proposed algorithms are implemented and evaluated through experiments with real data.