A situation caused by two or more processes being unable to proceed (and thus release their locks) because they are blocked by locks on resources held by the other process.
A deadlock occurs when two or more processes acquire locks on resources needed by the other process and then block because they are waiting for that process to release locks on resources that they require. The processes will then wait indefinitely on the locks to be released by the other process; as the process holding the locks is blocked, the locks will never be released.
A deadlock situation can occur when two processes acquire locks on the same resources in a different order. For example, we have objects A and B, and processes 1 and 2.
Process 1 (P1) acquires a lock on object A
Process 2 (P2) acquires a lock on object B
P1 tries to acquire a lock on object B but blocks because object B is locked by P2.
P2 tries to acquire a lock on object A but blocks because object A is locked by P1.
In this situation, process 1 and process 2 will remain blocked as they are waiting on locks that will never be released because they are held by a process blocked on a lock request for an object they hold a lock on. As neither process can proceed the locks will never be released.
Deadlock Detection Database management systems maintain an internal record of which objects (database records etc.) are held by locks obtained by which transactions. This record forms a graph structure that can be traversed by standard graph searching algorithms. The DBMS detects deadlocks by periodically sweeping the graph structure searching for cycles (circular references).
A cycle in the graph implies two or more processes are blocked waiting on resources on which the other holds locks (the cycle can involve more than two processes). When this is detected the deadlock resolution system will select one process and kill it. In Oracle the statement is rolled back, but the process is not killed and previous statements are not committed or rolled back.
Deadlocks are frequently caused by un-indexed foreign keys, multi-table modification operations done in differing orders, or simply improper explicit user locking.
Relevant Questions: Oracle 11g hunting down the deadlock