Data quality has attracted attention in theoretical database research in the past few years
and different aspects, such as consistency, accuracy, currency, and completeness have
been investigated [
As motivating example consider the student registration at the University of BozenBolzano. In November the student office distributed a report showing the numbers of students enrolled in the offered courses. When comparing the numbers with those of the previous years, the Master in Computer Science (MScCS) showed a decrease, in contrast with other courses, like the Master in Economics (MScECO), that registered a substantial increase. The reason for this discrepancy was a complication in the registration process, which foresees two routes to registration: an ordinary one and a second one via international federated study programs to which some Bolzano courses, like the MScCS, are affiliated. Due to different deadlines, ordinary registration was concluded in November while registration for students from federated programs was not. Since the MScCS is affiliated to some federated programs, but the MScECO not, the query asking for all MScECO students was stable in November and returned a reliable figure, while the query for all MScCS students was not and returned too low a number.
Even though in general a database may be constantly updating, and thus making data unstable, certain queries may have stable answers, (at least for some period of time). Registration at our University follows strict rules and is supported by an information system. If not only the data of the registration process were explicitly available, but also the rules, such a stability analysis of query answers could potentially be automated.
Assuming that data are created and manipulated according to a given business process, a formal reasoning task is to determine whether in all possible executions of such a process, the answer to a given query will remain the same. Then we say that the query is stable, and therefore reliable.
In this work, we propose a simple yet expressive formalism to model business processes that read, create and write data in an underlying database. We leverage the formal definition of such a business process to deduce whether a query answer is stable in case the data is managed according to the rules of the process. We establish exact complexity measures for checking the stability of conjunctive queries in several variants of processes. Since our upper complexity bounds stem from reductions to the evaluation of certain FOL and Datalog queries, our work provides an immediate way for implementations using technologies such as SQL and ASP engines.
Related Work. Traditional approaches to business processes modeling are
activitycentric and are based on (high-level) Petri Nets [
With our model of data-aware business processes (DABP) we want to capture some elementary aspects of how data are manipulated by business processes. A DABP over a schema is a pair B = hP; Ci, consisting of a process part P and a configuration part C. Intuitively, the process part is fixed. It defines how and under which conditions actions can change data stored in the configuration part. The configuration part comprises an instance of the underlying database and the state of all active process instances. Process Part. The skeleton of the process part is a directed potentially cyclic graph N = hP; T i, the process net, consisting of a set of vertices P , the places, and a set of edges T , the transitions. There is one distinguished place in P , the start place start. There is also a distinguished relation symbol, I, the input of a process instance. The last argument of I is a timestamp , called the start time, to record the time when the process instance was started. We denote the schema augmented by I as I . In a process instance, an object holding an I-atom traverses the graph, starting from start. Thus, the different transitions emanating from a place represent alternative developments of a process instance.
The whole process part is a pair P = hN; Li, which in addition to a network N comprises a labeling function L that assigns to every transition t 2 T a pair L(t) = (Et; Wt). Here, Et, the execution condition, is a Boolean query over I and Wt, the writing rule, is a rule Qt(x) ! R(x) whose head is a relation of and whose body is a
I -query that has the same arity as the head relation. Evaluating Wt over a -instance D results in the set of ground atoms Wt(D) = fR(c) j c 2 Qt(D)g. Intuitively, Et specifies in which state of the database which object can perform the transition t and Wt specifies which new information is (or can be) written into the database when studyplan program registr. master emSE affil mscCS emCL affil mscCS emCL ord mscCS db ord mscCS econ ord mscECO
admitted student program bob emCL mary emSE
deadline registr. date ord 1st Oct affil 1st Dec registered student master program bob mscCS emCL affiliated
start ordinary
a_late admitted
a_ontime refuse accept register
end o_ontime acad check o_late
reject Eaffiliated = I(S; P; T ); studyplan(P; affil; M ) Eordinary = I(S; P; T ); studyplan(P; ord; M ); :studyplan(P; affil; M ) Eadmitted = I(S; P; T ); admitted(S; P )
Erefuse = I(S; P; T ); :admitted(S; P ); studyplan(P; ord; M )
Ea late = I(S; P; T ); deadline(affil; D); T > D Ea ontime = I(S; P; T ); deadline(affil; D); T < D Wregister = I(S; P; T ); studyplan(P; R; M ) ! registered(S; M; P )
Eo late = I(S; P; T ); deadline(ord; D); T > D Eo ontime = I(S; P; T ); deadline(ord; D); T < D Eregister = Eaccept = Ereject = true performing t. In this paper we assume that Et and Qt are conjunctive queries with negated atoms and possibly comparisons involving timestamps.
Example 1. Consider again the scenario described in the Introduction. Table 1(a) contains a graphical representation of a DABP process net for a simplified student registration process, together with execution conditions and writing rules.
A student who wants to register to a program needs to fill a form providing her name and the program she wants to apply to. When received by the administration, the request is associated with a timestamp. We represent this information by a ground atom I (s; p; ) of the relation I . The available programs are of two kinds: those that are affiliated to international federated programs, and ordinary ones. For federated programs, an international commission decides about whom to admit and these decisions are stored in the table admitted. For ordinary programs, the university takes the decision.
According to this distinction, the first check in the process is to determine to which kind of program the request I refers to: affiliated (Eaffiliated) or ordinary (Eordinary). In the first case, a student who is already admitted to the federated program can proceed towards registration. Non-admitted students can go for an ordinary registration provided the program is open also to this kind of students (Erefuse). In case the student is admitted to the federated course, then the corresponding deadline for the application is looked up in the database: if the request arrived after the deadline (Ea late) then the registration process ends. Otherwise, if the request arrived on time (Ea ontime) the student is registered (Eregister) and a corresponding atom is inserted into the database instance (Wregister). Similarly, for a late ordinary request (Eo late) the process is ended, while for a request arrived on time (Eo ontime) the academic merits are checked (acad check). This human intervention is modelled as a non-deterministic choice that can result in the request being accepted (Eaccept) or rejected (Ereject). If accepted, the student is registered. Configuration Part. This part models the data that is manipulated by the process part. Formally, a configuration is a quadruple hD; O; M; i, where D is an instance of the schema , O is a set of process instances, which we call process objects, M is a mapping that associates every object o 2 O with a place MP (o) 2 P and with a ground I -atom I (c) = MI (o), and is a timestamp, the current time. We assume that for all objects o 2 O the start time in MI (o) is less or equal than the current time. Example 2. Table 1(b) shows a simplified database instance for our reference scenario. Relation studyplan stores the study programs offered by the university, the kind of registration they allow (ordinary or affiliated), and the master they belong to; admitted contains the students already admitted to a federated program; deadline stores the registration deadlines for the registrations to ordinary and affiliated courses; registered contains the students that successfully completed the registration process.
We consider an input relation I of arity 3, carrying the following information about the request: (i) the student name; (ii) the requested program; and (iii) the time of the request. In our example, there are no objects currently in the net.
Execution of DABP. Let B = hP ; Ci be a DABP, with current configuration C = hD; O; M; i. There are two kinds of atomic execution steps of a DABP, (i) the traversal of a transition in the net by an object or (ii) the introduction of a new object. Traversal of an enabled transition by an object. Consider an object o 2 O with M (o) = (p1; I (c)). That is, o is at place p1 and I (c) are the input data of o. Let t be a transition from p1 to p2, with execution condition Et. Then we say that t is enabled for o if D [ fI (c)g j= Et. Let Wt = (Qt(x) ! R(x) be the writing action of t. Then the effect of o traversing t is the transition from C = hD; O; M; i to a new configuration C0 = hD0; O; M 0; i, such that (i) D0 = D [ Wt(D [ fI (c)g) is the new database; (ii) the set of objects and the current time is the same, and (iii) M 0 is an update of M that reflects the change of place, that is, M 0(o) = (p2; I (c)) and M 0(o0) = M (o0) for all other objects o0.
Introduction of an arbitrary object at the start place. Let o0 be a fresh object and let I (c0; 0) be an atom where c0 is a vector of constants, and the timestamp 0 is greater or equal than C , the current time of C. Note that the constants in c0 need not appear in the database or in the process. The result of introducing o0 with info c0 at time 0 is the configuration C0 = hD; O0; M 0; 0i, where (i) the database instance is the same as in C; (ii) the set of objects O0 = O [ fo0g has been augmented by o0; and (iii) the mapping M 0 is an extension of M to O0, obtained by defining M 0(o0) = (start; I (c0; 0)) and M 0(o) = M (o) for all o 2 O.
An arbitrary execution is a sequence of atomic execution steps. Since for every configuration C one can introduce new objects at the start place, there are always several atomic executions possible for C. We say that a configuration C0 is reachable from C if there exists a finite sequence of atomic executions, such that C is the first and C0 is the last configuration in the sequence.
Finally, we define the property of query stability.
Definition 1 (Query Stability). Given a DABP B = hP ; Ci and a CQ Q. Then Q is stable in B if for any reachable configuration C0 = hD0; O0; M 0; t0i holds:
Q(D) = Q(D0): We illustrate this property with our running example. Consider the queries Qcs(S) registered(S; mscCS; P ) and Qeco(S) registered(S; mscECO; P ) that ask for the students registered at the master in CS, and the master in Economics, respectively. Depending on the current time, one can analyze the stability of the two queries. If the current time is before the 1st of October both queries are unstable since arbitrary new students can register. If the current time is after the 1st of December, both queries are stable since the two deadlines have passed. When the current time is between two deadlines, Qeco is stable because the deadline for ordinary programs has passed and mscECO is not affiliated to any program. On the other hand, Qcs is not stable because it is affiliated to the program emSE, for which mary did not register yet. Note that if she was registered, Qcs would be stable since all admitted student would be registered. 3
We investigated how to check whether a conjunctive query Q is stable in a DABP B. To understand the possible sources of complexity, we studied several types of processes that differ in the way they interact with the database and the way data can be entered into the process.
The first distinction is whether the model allows a process object to read the facts that itself or another object has written into the database. In the general case, denoted DABP, this is allowed. The restricted case, denoted DABProwo (read-only write-only), does not allow this. Formally, it splits the schema into disjoint schemas, the reading schema r and the writing schema w, such that the execution conditions and the queries in the writing rules range over r while the heads range over w. Our running example is in DABProwo.
We consider a process under open semantics, where new process objects may start in any moment. Alternatively, we also consider a process under closed semantics, that is we only admit transition traversals as possible execution steps (no new instances can be started). In this case, stability of a query depends only on the unfinished objects, while in open processes, it depends also on new objects that may start.
We also distinguish the case in which the initial configuration of the process does not contain any object, called fresh DABP, from the arbitrary case in which we do not make any assumption on the presence or absence of objects. Notice that under closed semantics the only interesting case is the arbitrary one (in a closed DABP with a fresh configuration a query answer is trivially stable since no objects can be inserted).
Table 2 summarises the complexity of checking stability for the different cases. Due to the limited space, we provide a brief intuition of the results while omitting the technical details. In general case, DABP allows unboundedly many new objects (data values) which combined with negation allows us to encode halting problem. Decidability is obtained either by disallowing negation (cases in brackets) or by disallowing new objects (closed semantics). For decidable cases, we established a correspondence between checking stability and brave entailment in Datalog with negation under stable model semantics. Similarly, for DABPs without negation we established a correspondence with entailment in positive Datalog. In the case of DABProwo, the complexity drops significantly due to the “non-recursive” rules. In particular, stability can be decided by FOL
Data UNDEC. (CONP)
P 2 P 2
(EXPTIME)
(EXPTIME)
Data Process Query Combined in AC0 CONP in AC0 CONP query evaluation. Given a DABProwo and a query we are able to encode the process part and the query into a FOL query that evaluates to true over the configuration iff the original query is not stable. The result of query complexity follows from the fact that deciding whether the two answers of a conjunctive query over two databases are the same is 2P-complete in the query size. 4
In this work we investigated the problem of determining the stability of a query answer when data is manipulated by a business process. As future work we plan to develop the DABP formalism further in the following ways: (i) consider more expressive queries, e.g., CQ: or FO; (ii) consider stability of aggregate queries and introduce aggregates in the process rules; (iii) quantify instability (in case a query is not stable, compute the minimal and maximal number of possible new answers, e.g., newly registered students); (iv) consider data quality aspects such as data timeliness and data currency. Acknowledgements. This work was partially supported by the projects MAGIC and RARE, funded by the Province of Bozen-Bolzano.