Methods for asynchronously determining relational data integrity using cryptographic data structures are performed by systems and devices. Changes in current tables of relational databases are reflected in associated history tables. Cryptographic hybrid blockchain ledgers are updated with transaction records, for entry changes in current and history tables, including transaction information and hash values of corresponding entry changes. Hybrid blockchain ledgers also include root hash values of Merkle trees of transaction records in current blocks, and hash values of prior blocks. A current block receipt is asynchronously generated and provided as a single hash value from which the validity states of the tables and ledger are able to be verified. Cryptographic receipts of specific transactions reflected in table entry changes are generated and provide immutable evidence of specific transaction existence for users. Ledger-enabled tables are provided for mixed database operations with ledger-disabled tables, and temporal history table database operations are enabled.