Some database features, such as SELECT ... FOR UPDATE and ON DELETE CASCADE, are implicitly vulnerable to deadlocks because the database does not specify what locking order will be used. I found two discussions that hint that this behavior isn't specified by the SQL standard, not to mention specific implementations. As such, I'm operating under the assumption that we cannot control the locking order (at least, it's not obvious how to do so).
How are we supposed to avoid database deadlocks if we cannot rely on the locking order?
If we're not supposed to avoid deadlocks (you're going to have to fight very hard to convince me of this) then what are we supposed to do?
This question is meant to be database-agnostic so please don't ask me which database I'm using.
A few years wiser, I am revising the accepted answer to state that database deadlocks cannot be prevented.
If you are lucky enough to be able to break down database operations to only interact with a single table at a time (something that isn't always possible) then you are forced to choose between poor performance and the possibility of deadlocks. Pick your poison.