Generalizing partial orders: A relation $R$ is transitive if $R \circ R \subseteq R$ and interpolative if $R \subseteq R \circ R$. It is idempotent if $R \circ R = R$. Interpolativeness means that whenever $x R y$ there is a "witness" to this: a $z$ such that $x R z$ and $z R y$. Idempotent relations generalize partial orders because a reflexive relation is always interpolative: take $z$ to be $x$ or $y$.
A transition from $x R y$ to $x R z R y$ can be thought of as a reduction step, so interpolative relations are in a sense amenable to computation. But note that if $x R z$ or $z R y$ are not more primitive than $x R y$ itself you may get a divergent computation.
A notable example of an idempotent relation from computer science is the way-below relation $\ll$ of domain theory. The theory of "abstract bases" of domains lies on the assumption that $\ll$ is actually more important than the preorder of the domain.
Categorification: there is a well known process of categorification that replaces partial orders with categories and during which transitivity and reflexivity become composition and identity of arrows. It is not difficult to generalize the notion of category to get a categorified version of idempotent relations. We keep composition but replace identity on objects with an splitting requirement on arrows: given $f: A \to B$ there is always an object C and arrows $g: A \to C$ and $h: C \to B$ such that $f = h \circ g$. Again if any of $A$ or $B$ admits an identity then $f$ has a trivial splitting. Note that this generalization of the notion of "category" is, from certain (maybe very narrow) sense, more symmetric than the usual definition and it allows objects which may be invisible in a usual category.
Of course categories would not be as interesting if they were not so abundant in mathematics. Now my question is this: is there any treatment of these "categories" in the literature? Do you know any natural example of such a "category"?