  Modern blockchain systems are a fresh look at the paradigm of distributed
computing, applied under assumptions of large-scale public networks. They can
be used to store and share information without a trusted central party. There
has been much effort to develop blockchain systems for a myriad of uses,
ranging from cryptocurrencies to identity control, supply chain management,
etc. None of this work has directly studied the fundamental database issues
that arise when using blockchains as the underlying infrastructure to manage
data.
  The key difference between using blockchains to store data and centrally
controlled databases is that transactions are accepted to a blockchain via a
consensus mechanism. Hence, once a user has issued a transaction, she cannot be
certain if it will be accepted. Moreover, a yet unaccepted transaction cannot
be retracted by the user, and may be appended to the blockchain in the future.
This causes difficulties as the user may wish to reissue a transaction, if it
was not accepted. Yet this data may then become appended twice to the
blockchain.
  In this paper we present a database perspective on blockchains by introducing
formal foundations for blockchains as a storage layer that underlies a
database. The main issue that we tackle is uncertainty in transaction appending
that is a result of the consensus mechanism. We study two flavors of
transaction appending problems: (1) the complexity of determining whether it is
possible for a denial constraint to be contradicted, given the state of the
blockchain, pending transactions, and integrity constraints and (2) the
complexity of generating transactions that are mutually (in)consistent with
given subsets of pending transactions. Solving these problems is critical to
ensure that users can issue transactions consistent with their intentions.
Finally, we chart important directions for future work.
