Software systems and the availability of data collecting devices lead to large amounts of data in the form of event streams. The ability to query, analyze, reason about, and monitor event streams is in high demand. In this work, we formalize a model of events and event streams in workflow systems, and a constraint language by extending Datalog with timestamp variables and gap constraints (inequalities with constant ofsets) over a time domain. We illustrate an application of our language by expressing rules with time constraints and data dependencies for workflow systems, where event streams from workflow enactments are monitored in real-time to ensure compliance with policies, regulations, and business rules.
(which uses window operators for expressing intervals, instead of time variables that can be
used in multiple (in)equalities), and “temporal” Datalog [
In Sec. 2 we formalize a model of events and event streams, and present the constraint language. In Sec. 3, we describe the monitoring and early detection problems and present relevant results. Finally, we discuss generalizations of these results and further applications in Sec. 4.
In this section, we present a language for writing constraints on events in workflow enactments.
The language is a variant of Datalog with two notable distinctions: the use of (i) timestamp
variables, and (ii) multiple atoms in a rule head. Furthermore, we adopt rules as constraints
rather than for deriving facts, which means the satisfaction of constraints by enactments is the
primary concern, rather than the deduction of new facts. This makes our language a natural
extension of tuple- and equality-generating dependencies [
We assume the existence of six countably infinite, pairwise disjoint sets of: activity names A, attributes C, discrete and ordered timestamps T, (data) values D, variables V, and (workflow) enactment identifiers , or simply ids, I. Without loss of generality, we use the natural numbers N as timestamps.
Activities are atomic units of work in a workflow, each with a name and data attributes. The execution of an activity produces an “event” at a timestamp at which the activity’s data attributes obtain values.
Definition: An activity (c1, ..., c) has a name ∈ A and an enumeration of (⩾ 0) distinct attributes c1, ..., c from C. An event of (c1, ..., c) is a tuple =(, , , ) where ∈ T is a timestamp, ∈ I an id, and : {c1, ..., c} → D a mapping to data values.
A partial enactment of a workflow system is a set of events such that (i) all events share the same enactment id, (ii) there is exactly one special START event (that marks its beginning) and at most one END event (that marks its completion), (iii) the timestamp of START is less than that of all other events, and (iv) the timestamp of END, if it is present, is greater than that of all other events. An enactment is a partial enactment that contains an END event.
A (partial) enactment can be stored as a relational database, e.g., the database in Fig. 1 for an enactment with id 1. For example, the first row of the Request table indicates a Request event for 1 from user Alice with account 3 at time 2.
To express constraints on enactments, we use a language introduced in [
Start ID 1 ts 1
ID 1 1
Request user account ts ID Alice a3 2 1 Alice a4 6
Payment ID user account ts 1 Alice a3 8 1 Alice a4 9
Approval user Alice Definition: A rule is an expression “ → ” where (the body) and (the head) are sets of event and gap atoms such that each variable in a gap atom in occurs in an event atom in and each variable in a gap atom in occurs in an event atom in ∪ .
Example 1. Consider an IaaS provider that ofers high-performance cloud computing rentals. The service is managed by a workflow with activities like Request and Payment, which carry attributes like user and account. Fig. 1 shows a partial enactment of the workflow. Consider that the IaaS provider checks enactments against business rules; these rules may measure service availability, quality, etc. The provider has the following rule:
This rule 1 indicates that a payment for a rental must be completed within 7 days of the request by the same user and account. Observe that the timestamp of the Request event and the timestamp of the Payment event are constrained to give an upper bound (or “deadline”) for the payment.
A second rule 2 requires the presence of Reserve and Payment events (with a matching user and account) given certain Request and Approval events: In 2, the timestamp variable in the body constrains another timestamp variable in the body, restricting which pairs of events trigger 2. Also, and in the body both constrain , in the head.
Rule satisfaction is defined for enactments using variable assignments: an assignment is a mapping from V to D ∪ T: timestamp variables are mapped to T and all other variables to D. An assignment is complete if it is a total mapping for the variables in an atom (or set of atoms). An enactment satisfies an event atom (1, ..., )@ under a complete assignment if ( (), , , (1), ..., ()) is an event in and is the id of . Let : (¯, ¯) → (¯, ¯) be a rule with distinct variables ¯, ¯, ¯. An enactment satisfies if satisfies the formula ∀¯¯( (¯, ¯) → ∃¯ (¯, ¯)) in first-order logic; a violation of is an assignment such that satisfies with and there is no assignment that extends such that satisfies with .
In this section, we describe an application of rules for monitoring enactments studied in our
recent work [
The rule satisfaction problem is to test if specified rules are satisfied by a (complete) enactment. Often, however, it is possible to know a rule violation is inevitable before the enactment is complete if the violation is present in all of its possible futures. Consider 1 in Ex. 1, a Request event at time is a violation if no Payment event is observed by time + 7. Then, a violation can be reported before the enactment completes once time + 8 is observed. It is advantageous to monitor the inevitability of violations as the partial enactment is updated. To formulate the monitoring problem, each partial enactment is treated as a relational database, and a “batch” holds the set of incoming events.
Definition: A batch for a partial enactment is a finite set ∆ of events such that (i) all events in ∆ have the same timestamp, greater than all timestamps in , (ii) the id of each event in ∆ is the id of , (iii) if ∆ has START, is the empty set, and (vi) if has END, ∆ is the empty set.
Given a partial enactment and a batch ∆ , the (online) monitoring problem is to decide if every enactment containing the union ∪ ∆ violates a (set of) specified rule(s).
In [
In [
satisfies if satisfies the LTL formula .
We also studied the monitoring problem for the general class of rules, including enactments
with data. Consider 2 in Example 1, events Request and Approval at times and , resp., with
⩽ ⩽ +7. There may be a violation at the earlier of +3 and +7 if the corresponding head
event doesn’t arrive. Calculating the earliest time a violation becomes inevitable is the early
detection problem. Notably, detecting violations early is much desired as it may, for example,
allow the workflow system to reclaim resources from erring enactments. In [
The algorithm in [
Complex temporal constraints occur in many application domains (IoT, cyber-physical systems, etc.). For IoT devices, memory and network limitations demand space-eficient algorithms for stream processing and tolerance of out-of-order events. In cyber-physical systems, violations must be anticipated as early as possible so that the system can maintain a safe state; this requires studying early detection for constraints that mix time, space, and other resources. Finally, it is desirable to have rules that check for the absence of events, generate facts, and allow summaries and aggregates, alongside rules that express constraints.