We examine the problem of determining whether a given set of locked transactions, accessing a distributed database, is free from deadlock. A deadlock graph is used to derive a new characterization for deadlock-free two-transaction systems in a distributed environment. The characterization provides a direct and efficient polynomial test for deadlock-freedom in two-transaction systems. The method is not dependent on the number of sites in a distributed database, and hence improves previously known results, which are exponential in the number of sites.