Clouds (Partially Order Sets) – Streams (Linearly Ordered Sets) – Part 1
We read interesting discussions in the CEP and ESP market regarding terms like “clouds” and “streams”. Sometimes we observe folks talking about these terms in context of “processing time”, for example, reordering events as part of computational event processing.
A closer examination of posets and linearly ordered sets leads to an understanding, or formality, which is independent of the computational requirements. Sets, formally, are finite or infinite collections of objects (in our case, events) in which order has no significance, and multiplicity is generally ignored. Relations, in set theory, are any subset of a Cartesian product.
A relation R on a set A is called a partial order if R is reflexive, antisymmetric, and transitive. The set A together with the partial order R is called a partially ordered set or poset, and is denoted (A,R). This is what Dr. Luckham kindly reminds us is the formal definition of an “event cloud”.
If (A, R) is a poset, we say A is totally (linearly) ordered if for all x, y (in the set of) A either xRy or yRx. In this case R is called a total order. A linearly ordered set has the same three properties of posets (reflexive, antisymmetric, and transitive) with the addition of a forth, comparability (the trichotomy law). It is the addition of the property of comparability to posets that creates linearly ordered sets, what Dr. Luckham refers to as “event streams”.
The abstract properties of these events are based on the intrinsic relationships between events in the set, easily observed from the formal definitions of posets and linearly ordered sets. It follows that it can be independently shown, along this line of set theory analysis, that the metaphor “event cloud” is a partially ordered set of events and an “event stream” is a linearly ordered set of events. The different between the two is the forth additional property of comparability (the trichotomy law) applied to posets, creating the special case of posets called linearly or totally ordered sets of events.
Kindly keep in mind that we are discussing the intrinsic nature of events and event relationships (from set theory). For example, the fact that events arrive out-of-order (from a temporal perspective) demonstrates that there is order (it is a linearly ordered set). Also, please keep in mind that the term “relation” in this context can be a taxonomy, causality, partonomy, and/or temporal, for example. In other words, the temporal relationship often discussed in event stream processing is only one of a number of possible interesting relations in posets.
In a future post, I will endeavor to describe the significance of the set relationship principles of “event comparability” and “event incomparability” in the content of ESP (event comparability, event streams) and the general case of CEP (event sets where events are partially ordered and not necessarily comparable).