> It seems like everyone just explains the relational algebra, then leaves it right there.
Fair point.
> What is the exact nature of the complexity explosion you are talking about here?
I'm thinking in terms of the entities of Occam's razor: "entities should not be multiplied unnecessarily." "Entities" is pretty abstract, we can't identify what complexity is directly, but what we can do is imagine, "what if we tried to build a mathematical model that captures a real life application?"
If we did that, and had a mathematical description of a thing we wrote, we can formalize it by trying to reduce it to some minimal set of axioms.
And then, your more complex rules are derived from those axioms, and if you get your math right those complex rules will be consistent. If you're very clever, you can make it reasonably intuitive.
If you have something that's very complex, what you'd observe after modelling it is you have mostly axioms and very few rules are able to be derived from those axioms. That is, the rules are just the rules and there's no broader reason for them to be so, or deeper consistent patterns. And, maybe some of those rules wind up being contradictory, and they may lack orthogonality.
The relational algebra, being an algebra, is a set of operatations that are closed over the universe of relations, so it's very nicely orthogonal and reduces to a small set of primitives. As relations can be visualized as "tables" they're relatively intuitive, and using techniques such as normalization you can also structure around potential anomalies that add unwanted complexity.
You can also control where your complexity goes. An integrity constraint can enforce some rules about what may be in a relational variable, and if that's enforced, all code that wants to use data from that relation can simply assume that the data maintains that structure. Thus the complexity can be centralized in the system.
Now, that's in the ideal world with a True Relational DBMS, we have to deal with SQL and vendor-specific SQL at that, so we have a rather complex underlying model. But it's typically Pretty Good.
When we build such a model ad hoc, we go by our intuition and are constrained by the market. Our intutition leads us to use more complex structures, that is, structures that if they were expressed mathematically would use a larger set of axioms to describe them. Then, as we want those structures to interoperate, we are unwittingly merging two sets of axioms.
Worse, because we're typicaly expressing it in application libraries, we wind up repeating code, so the complexity is spread all over the application and it especially multiplies if "conventions" are copy-pasta'd.
Hopefully that explains the nature of the explosion of entities / complexity; let me know if I can expand on anything.