The usual method for preserving the consistency of a database when accessed (read and updated) concurrently by several transactions, is by locking the transactions according to some locking policy; a locking policy that guarantees the preservation of consistency of the database is called safe. Furthermore, if no deadlocks can arise the policy is called deadlock-free. In this paper we are concerned with the freedom from deadlock of safe locking policies. We show that a simple extension of the DAG policy of [Y] is the most general safe and deadlock-free policy for a pair of transactions. We prove however, that it is NP-complete to test whether a set of transactions is not deadlock-free even for the simplest kind of transactions, those that are two-phase locked [E]. We show that for the natural class of safe locking policies, the L-policies, studied in [Y], freedom from deadlock is determined only by the order in which entities are accessed by the transactions and not by the way in which safety is ensured. A...