Fuctional dependencies (FDs) form the foundations of database theory since the beginning of time, given they may represent constraints such as \the employee role determines his monthly salary". If we consider temporal databases where each tuple is timestamped with a valid time (V T ) attribute, ner constraints may be imposed on the evolution of the data such as \the employee role before a promotion and his role afterwards determine his new monthly salary". Such constraints are called Pure Evolving Functional Dependencies (PEFDs) according to the classi cation introduced in [3]. By adding approximation to such rules they may be used for extracting knowledge in place of imposing constraints. Then we may want to discover that \the employee role before a promotion and his role afterwards generally determine his new monthly salary". This kind of approximate dependencies are called Approximate Pure Evolving Functional Dependencies (APEFDs). Verifying whether or not a given APEFD holds over a database instance is an NP-Complete problem [4]. Despite the discouraging complexity, in this work we propose an algorithms that solve in an e cient way this problem by trying to divide-and-conquer and prune the search space as much as possible.
This work has not been previously published and it is an extension of the results
published in [
r J $ ' ' &u ' ' %
rptq^rpt1q^trJs t1rJs urJs^urW s trW s^ Dt;t1 urW s t1rW s^trV T s urV T s^t1rV T s urV T s ^trV T s t1rV T s^ /
/ @t2pprpt2q^trV T s t2rV T sqÑt1rV T s¤t2rV T sq , / / .
Schema Rev is called the evolution schema of R. We will denote by JR the view on R that is built by expression Jr for every instance r of R. View JR joins two tuples t1 and t2 that agree on the values of the attributes in J (i.e. t1rJ s t2rJ s) and t1rV T s t2rV T s. Moreover, such tuples are joined if does not exist a tuple t P r with trJ s t1rJ s and t1rV T s trV T s t2rV T s (i.e., there exists a tuple that holds at some point in between the valid times of such tuples). For application purposes, it is correct correct to consider in a evolution schema only those pair of consecutive tuples whose the di erence between V T and V T respects some given bound. Given a parameter k P N Y t 8u, tuples of Jr are ltered by means of the selection kp Jrq trV T s trV T s¤kp Jrq (notice that 8p Jrq Jr). kp Jrq forces to consider only those tuples belonging to Jr having a temporal distance within the given threshold k. In the following, given a tuple t P Jr, we denote its temporal distance trV T s trV T s with ptq.
A Pure Temporally Evolving Functional Dependency [
R r kp J qsXY Ñ Z:
We have that X W and Y ; Z W with X H and |Z| 1 (Z contains a single attribute). We say that an instance r of R ful lls a PEFD r kp JRqsXY Ñ Z, written r |ù r kp JRqsXY Ñ Z, if and only if for each pair of tuples t; t1 P kp Jrq we have trXs t1rXs ^ trY s t1rY s Ñ trZs t1rZs.
Now add approximation to PEFD in a very standard way [
R Gpr kp J qsXY Ñ Z; rq |r|
R maxt|s| : s r; s |ù r kp J qsXY Ñ Zu:
By means of G we can de ne the relative scaled measurement g for TM-FD as follows:
R gpr kp J qsXY Ñ Z; rq
Gpr kp JRqsXY Ñ Z; rq : |r|
Now we are ready to de ne the Approximate Pure Temporally Evolving Functional Dependency (APEFD for short). Formally, given a real number 0 ¤ ¤ 1, we say that an instance r of R satis es the APEFD r kp JRqsX Y Ñ Z, written r |ù r kp J qsXY Ñ Z, if and only if gpr kp JRqsXY Ñ Z; rq ¤ .
R
In Section 2 we provide an algorithm for checking an APEFD against an instance r, we call this problem Check-APEFD: Problem 1. (Check-APEFD). Given a temporal schema R, a PEFD r kp JRqs XY Ñ Z on R, an instance r of R, and a real number 0 ¤ ¤ 1 determine whether or not r |ù r kp JRqsXY Ñ Z. # Name P hys CT 1 M cM urphy Sayer self 2 M cM urphy Sayer f amily 3 M cM urphy M aguire f amily 4 M cM urphy M aguire self 5 M cM urphy M aguire self 6 M cM urphy M aguire self 7 Lowe Sayer f amily 8 Lowe Sayer f amily 9 Lowe M aguire self 10 Lowe Sayer self 11 Lowe M aguire self 12 Lowe Sayer self
Fig. 2. The evolution expression Nrame.
Now we consider a scenario, borrowed from the clinical domain, in order to provide examples of how PEFDs and APEFDs work. In particular, this scenario is taken from psychiatric case register. Let us consider the temporal schema Contact tN ame; P hys; CT; Duru Y tV T u. Such a schema stores values about a phone-call service provided to psychiatric patients. This service is intended for monitoring and helping psychiatric patients, who are not hospitalized. Whenever a patient feels the need to talk to a physician, he can call the service. Data about calls are collected according to schema Contact. For the sake of simplicity, temporal attribute V T identi es the day when the call has being received, not the exact time the call has begun which is usually its semantics in real world applications. In addition, the service may be used by people somehow related to patients, as, for instance, relatives afraid of current conditions of a patient. More precisely, attribute N ame identi es patients, P hys identi es physicians, CT (Contact Type) identi es the physical person who is doing the call (e.g., value 'self' stand for the patient himself, 'family' for a relative), and Dur stores information about total duration of calls (value n means approximately n minutes). An instance r of R is provided in Figure 1. Instance Nrame, and Jr in general, may be seen as the output of a two-phase procedure. First, table Contact is partitioned into subsets of tuples, one for each value of N ame. Then, each tuple is joined with its immediate successor in its partition, w.r.t. V T values. The whole relation Nrame is provided in Figure 2. In the following we will use t for referencing tuples of r and u for referencing tuples of Jr. Moreover, in the following each tuple u in Jr will be identi ed by the pair of indexes of the tuples in r that generate u. For instance, the rst tuple of Jr in Figure 2 will be denoted by u1;2 since it is generated by the join of tuples t1 and t2 in r.
Going back to our example, it is worth noting that tuples t2 and t7 are not joined in Nrame, even if t7rV T s t2rV T s 2 and there is no tuple t with trV T s t7rV T s 1. This is due to the fact that t7rNames t2rNames forbids the join in Nrame. Moreover, t1 and t3 are not joined in Nrame . Indeed, the presence of tuple t2 with t1rNames t2rNames t3rNames and t1rV T s t2rV T s t3rV T s forbids the join in Nrame . Figure 3 graphically depicts how pairs of tuples pt1; t2q; pt2; t3q; pt3; t4q; pt4; t5q; pt5; t6q and pt7; t8q; pt8; t9q; pt9; t10q; pt10; t11q; pt11; t12q are joined in Nrame . In both scenarios depicted in Figure 3, nodes represent tuples and are labeled by the corresponding tuple number. Values for attribute Dur are reported above each node. Values of P hys and CT attributes are reported below every node, respectively. Every edge pti; tj q is labeled by value pui;j q tj rV T s tirV T s (i.e., the temporal distance between two tuples). Basically, each tuple u P Nrame corresponds to an edge in Figure 3 while we have a node for each tuple in r.
In our example, we have that r |ù r 5p NCaomnteactqsP hys; P hys Ñ CT . However, r * r 6p NCaomnteactqsP hys; P hys Ñ CT , because of pairs pt2; t3q and pt10; t11q. More precisely, we have that t2rNames t3rNames M cM urphy, t10rNames t11rNames Lowe, t2rP hyss t10rP hyss Sayer, t3rP hyss t11rP hyss
In other words, we have that the set of tuples tu2;3; u10;11u does not satisfy the
Let us observe that the two proposed PEFDs di er only for the maximum temporal distance allowed. In particular, tuple u10;11 is responsible for r |zù r 6p NCaomnteactqsP hys; P hys Ñ CT and it does not belong to 5p NCaomnteactq because of pu10;11q ¡ 5 then we have r |ù r 5p NCaomnteactqsP hys; P hys Ñ CT . This allows us to point out a general property of PEFDs, such a property holds for APEFDs, too. Given a PEFD r kp JRqsXY Ñ Z we have that for every instance r of R such that r |ù r kp JRqsXY Ñ Z then for every h ¤ k we have r |ù r hp JRqsXY Ñ Z.
In our example, if we consider APEFD r 6p NRame qsP hys; P hys Ñ CT with 112 , we have that r |ù r 6p NRame qs P hys; P hys Ñ CT . It is worth noting that, by considering relation r1 rztt3u, this dependency would hold without the need of approximation (i.e., if tuple t3 is deleted from relation r). More precoirsiegliyn,awlley hinaveNraNrm1aembeecauNrseamoef zttuup2l;e3;tu3.3;F4 uigYutrue23;4du.epNiocttsictehtihsantetwupscleenua2r;4iow,absynroetplacing edges pt2; t3q and pt3; t4q with the dashed edge pt2; t4q. Moreover, we have that r1 |ù r 8p NRame qsP hys; P hys Ñ CT . Thus, r |ù r 8p NRame qsP hys; P hys Ñ CT with 112 . 2
As we proved in [
Then, in principle, there is no asimptoptycally better algorithm than explore the whole set of of possible subsets r1 of r with |r||r||r1| ¤ . However, in the following, we provide an algorithm that make use of heuristics for pruning the search space in order to achieve the tractability for many cases.
Such algorithm is general and it may be applied under no assumptions on the input instance r, it makes use of two optimization techniques. The rst optimization technique consists of trying, whenever is possible, to split the current subset of r in two subsets on which the problem may be solved independently (i.e., choices in one subset do not a ect choices in the other one and viceversa). The latter optimization technique consists of checking if the current partial solution may not lead to an optimal solution (i.e., a solution r1 where |r1| is the maximum possible number of tuples that may be kept) if this happen the subtree is pruned immediately (i.e., we are looking only for optimal solutions).
Our algorithm relies on the concept of color that we will explain through an example in the following. Given APEFD r JR; swpkqsXY Ñ Z and an instance r of R, let us suppose that we are solving problem Check-APEFD on such instance with a simple guess-and-check procedure that make use of two, initially empty, subset r (the tuples to be kept in the solution) and r (the tuples to be deleted in the solution) of r. At each step the procedure guess a tuple t in rzpr Yr q and decides non-deterministically (guessimg phase) either to update r to r Y ttu (i.e., t is kept in the current partial solution) to update r to r Y ttu (i.e, t is deleted in the current partial solution). When r r Y r (check phase), the procedure returns Y ES if r |ù r JR; swpkqsXY Ñ Z and |r | ¤ |r|, otherwise it returns N O. From now on, for us a partial solution is a triple pr; r ; r q such that pr Y r q r and r X r H, if r r Y r we simply say that pr Y r q is a solution. A solution is consistent pr; r ; r q if and only if r |ù r JR; swpkqsXY Ñ Z. Given two partial solution pr; r1 ; r1 q and pr; r2 ; r2 q we say that pr; r2 ; r2 q extends pr; r1 ; r1 q if and only if r1 r2 and r1 r2 .
Is there a way to check if we are generating an inconsistent solution possibly without guessing all the tuples in r? Violations of the latter constraint (i.e., |r | ¤ |r|) are fairly simple to detect during the guessing phase, it su ces to check after each insertion in r if r exceeds |r|, if it is the case the procedure may return N O immediately without guessing any further. Violations of the rst constraint (i.e., r |ù r JR; swpkqsXY Ñ Z) during the guessing phase are trickier to detect, then we need the following additional de nitions. From now on when two tuples t; t1 share the same value for the attribute J (i.e., trJ s t1rJ s) we will say that they are in the same J -group and we will say that trJ s is the value of the J -group containing t and t1. For the sake of brevity, for a given j P DompJ q we will use j-group for denoting the J -group with value j. An ordered pair, written o-pair, is a pair pt; t1q P r r such that t and t1 are in the same J -group and trV T s t1rV T s. Given an o-pair t; t1 P r we say that the pair pt; t1q is an edge if and only if 0 t1rV T s trV T s ¤ k. Given triple pr; r ; r q, an o-pair pt; t1q P r is active if and only if t; t1 P r and for every tuple t in the same J -group of t if trV T s t t1rV T s we have t P r (i.e., t and t1 are selected in the current partial solution and all the tuples between t and t1 in the same J -group are deleted). Given two valid times vt; vt1 P DompV T q and a value j P DompJ q we say that vt and vt1 are consecutive in j-group if and only if there exists an active o-pair pt; t1q with trV T s vt, t1rV T s vt1, and trJ s j. Notice that we may have two distinct values j; j1 P DompJ q and two distinct valid times vt; vt1 P DompV T q which are consecutive in j-group and not consecutive in j1-group. Moreover, we may have edges pt; t1q that are not active and active pairs pt; t1q that are not edges, such is the case of active pairs pt; t1q with t1rV T s trV T s ¡ k. A color is a tuple c on the schema C XY Z, two colors px; y; zq and px1; y1; z1q are con icting if and only if x x1, y y1 and z z1. Given an o-pair pt; t1q, denoted by cpt; t1q is the tuple cpt; t1q ptrXs; trY s; t1rZsq. Two o-pairs pt; t1q; pt2; t3q are con icting if and only if cpt; t1q and cpt2; t3q are con icting. The following result it is easy to prove and its proof is left as exercise for the reader.
Theorem 1. Given an APEFD r JR; swpkqsXY Ñ Z, an instance r of R, and a partial solution pr; r ; r q, if there exists two active edges pt; t1q and pt2; t3q then every solution pr; r f ; r f q that follows pr; r ; r q satisfy rf z|ù r JR; swpkqsXY Ñ Z (i.e., is inconsistent).
The above theorem guarantees that from a partial solution pr; r ; r q that feature at least two con icting edges we cannot reach a solution pr; r f ; r f q that satisfy the rst constraint and in such a case we may return immediately N O without going any further from pr; r ; r q. The colours of a partial solution pr; r ; r q is the set colourspr; r ; r q tptrXs; t1rY s; t1rZsq : pt; t1q is an active edge in pr; r ; r qu. It is easy to see that the hypothesis of Theorem 1 applies if and only if colourspr; r ; r q contains at least two con icting colours. Then, by means of colours, our above guess-and-check procedure may be improved by adding the control on the size of r and by keeping updated the current set of colours colourspr; r ; r q. Once an insertion of a tuple in either r or r introduce a color c that is con icting with at least one colour in pr; r ; r q the procedure answers N O immediately.
An example of how the procedure works is given in Figure 4 where we have an instance of 5 tuples with 0:2 (i.e., we may delete at most one tuple) and swpkq 6 (all the tuples are in the same window). The execution depicted in Figure 4 guesses the values of the tuples from the oldest (t1) to the newest one (t2) according to the value of V T . First it tries to put the current tuple t in r if no violation arises it continues, if some violation arises it tries to insert the tuple t in r if no violation arises it continues otherwise it goes back to the previous choice (i.e., backtracking). Every internal node is labelled with the current tuple which will be guessed next, every leaf is labelled either with Y ES (i.e., the current branch is a solution) or N O (i.e, a violation has arisen), the current set of colours is reported within the node. Nodes are numbered according to their order of appearance. We have that the root is n1 followed by the introduction of the nodes n1 : : : n4 in this precise order. If we introduce t4 in the partial solution associated to n4 we violate the rst constraint. Since in n4 adding t4 in r does not generate any violation, node n5 is created as child of n4. However, node px1;y1;z2q px2;y1;z2q px1;y1;z2q
px2;y1;z2q px1;y1;z2q px1;y1;z2q n5 cannot be extended without introducing a violation in the above constraints because if put t5 in r we introduce a con icting color, while if we put t5 in r we exceed the maximum number of allowed deletions. We backtrack to n4 and we have that even for it all the possible choices have been explored and thus we backtrack to n3 where the choice of adding t3 to r is attempted generating the node n6. From n6 we put t5 in r without violating any constraint and thus we have that tt1; t2; t4; t5u |ù r JR; 6sXY 0Ñ:2 Z.
Let us consider deeper in the description of the rst algorithm. On an higher lever the algorithm operates like the procedure above apart from some trivial technicalities. However, two more heuristics are introduced in order to possibly stop early during the exploration of a branch in the tree of computation. The main procedure of the algorithm is reported in Figure 7 with auxiliary procedures reported in Figure 5 and in Figure 6. The algorithm is implemented by the function T upleW iseM in that takes 4 arguments. The rst argument is Gr which is a pre-processing of r based on the APEFD r JR; swpkqsXY Ñ Z that has to be checked. More precisely, Gr is an instance of the schema J; X; Y; Z; V T; count, with Dompcountq N. We have that t P Gr if and only if there exists t1 P r for which pt1rJ s; t1rXs; t1rY s; t1rZsq ptrJ s; trXs; trY s; trZsq and trcounts |tt1 P r : pt1rJ s; t1rXs; t1rY s; t1rZsq ptrJ s; trXs; trY s; trZsqu|, that is, we count how procedure InBetweenpGr; t1; t2q comment: roefttu1rnasndthte2 stuhbastetfeoaftuGrer vcoanlisdisttiimngesobfeatlwltehene ttu1rpVleTs sinantdhet2sraVmTesJ. -group return tt P Gr : t1rV T s trV T s t2rV T s ^ trJ s t1rJ su procedure EdgeConflict?ppt1; t2q; pt11; t12qq comment: returns true if and only if the two input edges feature con icting colors. if t1rXs t11rXs ^ t2rY s then return true else return false t12rY s ^ t2rZs t12rZs if Dcpc P C ^ t1rXs then return true else return false procedure ColorConflict?ppt1; t2q; Cq comment: returns true if and only if the color of the edge pt1; t2q is con icting with at least one color in the set of colors C.
crXs ^ t2rY s crY s ^ t2rZs crZsq procedure E!pGr; k; Gr ; Gr q comment: rseotluutrinosn.the set of all and only active edges in the current partial return " pt1; t2q : t1rJ s t2rJ s ^ 0 t2rV T s t1rV T s ¤ k^ tt1; t2u Gr ^ InBetweenpGr; t1; t2q Gr q * procedure E?pGr; k; Gr ; Gr ; Cq comment: rseotluutrinosn.the set of all and only pending edges in the current partial $ ' ' return & ' ' %
t1rJ s t2rJ s ^ 0 t2rV T s t1rV T s ¤ k ^ tt1; t2u X Gr pt1; t2q : ^ ColorConf lict?ppt1; t2q; Cq^ ^InBetweenpGr; t1; t2q X Gr H^ ^ptt1; t2u Y InBetweenpGr; t1; t2qq pGr Y Gr q H^ /, / . / / procedure Reach?pt1; t2; N odes; Edgesq
returns true if and only if there exists a path from t1 to t2 in the graph comment: pN odes; Edgesq. It is a function that checks wether or not there exits a path between two nodes in a graph.
t1 ^ tm if Dptt1 : : : tmu N odesqpt1 then return true else return false
Fig. 5. Auxiliary procedures used by procedures presented in Figures 6 and 7. procedure GroupIndependent?pj; Gr; k; Gr ; Gr ; Cq
returns true if and only if in the current partial solution pending edges comment: involving tuples belonging to the J -group with value j are not con icting with the pending edges introduced by the others J -groups. Ej Ð tpt1; t2q P E?pGr; k; Gr ; Gr ; Cq : t1rJ s ju Ej Ð E?pGr; k; Gr ; Gr ; CqzEj if Dt1Dt2Dt1Dt2ppt1; t2q P Ej ^ pt;t2q P Ej ^ EdgeConf lict?ppt1; t2q; pt1; t2qqq then return false else return true procedure MacConsistentSubsetpEq
returns the maximal subset E1 of E such that d for every edge comment: pt11; t12q P E1 and for every edge pt1; t2q P E we have that cpt11; t12q and cpt1; t2q are not con icting.
E1 Ð H return E1 for each pt1; t2q P E do "ift@hte1n@t2Ep1ptÐ1; tE2q1 YPEtptÑ1; t2qEudgeConf lict?ppt1; t2q; pt1; t2qqq procedure ReplacePath?pt; t; Gr; k; Gr ; Gr ; Cq comment: returns true if and only if in the current partial solution the consecutive valid times trV T s and trV T s in trJ s-group may be safely replaced. if Dt1pt1 P Gr ^ t1rJ s trJ s ^ trV T s t1rV T s trV T sq
then return false Ns Ð tt1 P Gr : t1rJ s trJ s ^ t1rV T s trV T su Ne Ð tt1 P Gr : t1rJ s trJ s ^ t1rV T s trV T su Nm Ð tt1 P Gr : t1rJ s trJ s ^ trV T s t1rV T s trV T su N Ð Ns Y Ne Y Nm E~ Ð tpt1; t2q : t1 P N ^ t2 P N ^ t1rV T s t2rV T s ^ pt1 R Ns _ t2 R Nequ P airs Ð tpt1; t2q : t1 P N ^ t2 P N ^ t1rV T s k t2rV T s ^ pt1 R Ns _ t2 R Nequ E~ok Ð pM axConsistentSubsetpE?pGr; k; Gr ; Gr ; Cqq X E~q Y P airs N otSaf e Ð H for each pt1; t2q P E~zE~ok
$&for each pt1; t2q P pE?pGr; k; Gr ; Gr ; Cq Y E!pGr; k; Gr ; Gr q Y E~q do % do "iftEhedgneCNoontSf laifcte?Ðppt1N; to2tqS; aptf1e; tY2qtqpt1; t2qu E~ Ð E~zN otSaf e
Fig. 6. Auxiliary procedures used by procedure T upleW iseM in (Figure 7). Algorithm 2.1: TupleWiseMin(Gr; k; Gr H; Gr
H; C procedure MaximalPaths?pGr; k; Gr ; Gr ; Cq
returns true if and only if in the current partial solution for every comment: J -group j-group every pair of consecutive valid times vt and vt1 in j-group cannot be safely replaced. if Dt1Dt2ppt1; t2q P E!pGr; k; Gr ; Gr q ^ ReplaceP ath?pt1; t2; k; Gr; Gr Gr ; Cqq then return false else return true procedure IsConsistent?pGr; k; Gr ; Gr ; Cq
returns true if and only if the current partial solution features comment: consistent colors in C and for every J -group j-group every pair of consecutive valid times vt and vt1 in j-group cannot be safely replaced. if Dt1Dt2ppt1; t2q P E!pGr; k; Gr ; Gr q ^ ColorConf lict?ppt1; t2q; Cqq
then return false if M aximalP aths?pGr; k; Gr ; Gr ; Cq then return true else return false main comment: returns the minimum value m min ||GrzG1r|| for G1r in tGr2 Gr : G1r |ù r GXrY ZcountsXY Ñ Zu. if Gr H then return ||Gr || if Djpj P DompJ q ^ GroupIndependent?pj; Gr; k; Gr ; Gr ; Cqq then &$Gr Ð tt PTGurpl:etWrJisseCjhueckpGr; k; Gr X Gr; Gr X Gr; Cq
%return T upleW iseCheckpGrzGr; k; Gr zGr; Gr zGr; Cq let t P Gr if IsConsistent?pGrzttu; k; Gr Y ttu; Gr ; Cq then "C1 Ð C Y tpt1rXs; t2rY s; t2rZsq : pt1; t2q P E!pGrzttu; k; Gr Y ttu; Gr qu mt Ð T upleW iseCheckpGrzttu; k; Gr Y ttu; Gr ; C1q else mt Ð 8 if IsConsistent?pGrzttu; k; Gr ; Gr Y ttu; Cq then "C1 Ð C Y tpt1rXs; t2rY s; t2rZsq : pt1; t2q P E!pGrzttu; k; Gr ; Gr Y ttuqu mzt Ð T upleW iseCheckpGrzttu; k; Gr ; Gr Y ttu; C1q else mzt Ð 8 return minpmt; mztq Fig. 7. The main procedure for checking APEFDs in a tuple-wise fashion. Notice that we use a compact notation for the recursive procedure which is initially called as T upleW iseM inpGr; kq where when Gr , Gr , and C are ommitted in the procedure call they get their respective default values speci ed in the procedure declaration (i.e., H for each of them in this case). many tuples in r share the same values for attributes J; X; Y; and Z. The input parameter k is the length for the sliding window grouping swpkq. The sets Gr and Gr , originally initialized to H, represent the tuples of Gr that are either kept or deleted in the current solution respectively. On instances r of schema R satisfying count P R we denote with ||r|| the sum on the count attribute for the tuples in r (i.e., ||r|| °tPr trcounts). Finally, C is a set of colors which is initially set to H. A color c is a tuple on the schema X; Y; Z. As we will see, C keeps track via colours of the constraints introduced so far in the construction of the solution.
The procedure T upleW iseM in returns the minimum number of tuples that has to be deleted from r in order to obtain an instance r1 such that r1 |ù r JR; swpkqsXY Ñ Z. Then if such minimum is less or equal than |r| we can conclude r |ù r JR; swpkqsXY Ñ Z else we have r |ùz r JR; swpkqsXY Ñ Z. Given Gr, Gr , Gr , and a set of colours C we say that an edge pt; t1q P Gr Gr is pending if and only if the following conditions hold:
2. for every t2 with t2rJ s trJ s and trV T s t2rV T s t1rV T s we have t2 R Gr ; 3. there exists t2 P pGr Y tt; t1uqzpGr Y Gr q with t2rJ s trJ s and trV T s ¤ t2rV T s ¤ t1rV T s.
Informally speaking, a pending edge is an edge that is not active in the current partial solution but it may become active during the computation and, if it happens, it introduces a new color in C. In our algorithm, pending edges for the current partial solution are retrieved by the procedure E? while active edges are retrieved by the procedure E!.
The procedure T upleW iseM in (Figure 7) works as follows. If Gr Y Gr Gr it means that we have obtained a solution without violating any constraint and thus we can return ||Gr || (i.e., the number of deleted tuples). If Gr Y Gr Gr the algorithm guesses a tuple t P GrzpGr Y Gr q and proceed as follows. First, it checks if inserting t into Gr does not cause any violation in the constraints, if so it stores in mt the value of the recursive call to T upleW iseM in where t belongs to Gr and C has been updated accordingly. Notice that by inserting a tuple t in Gr the algorithm is asserting that t belongs to the current partial solution, while by inserting t in Gr the algorithm is asserting that t does not belong to the current partial solution. If a constraint is violated the algorithm stores in mt the value 8, which means that t may not be kept in the current solution.
Then, it checks if inserting t into Gr does not cause any violation in the constraints, if so it stores in mt the value of the recursive call to T upleW iseM in z where Gr and C are updated accordingly. If a constraint is violated the algorithm stores in mzt the value 8, which means that t must be kept in the current partial solution. In procedure T upleW iseM in the only way in which a constraint may be violated is that, after the insertion a tuple t in Gr (resp. Gr ), an edge pt1; t2q turns out to be active and its color pt1rXs; t2rY s; t2rZsq turns out to be con icting with at least one color in C.
The rst one allows us to restrict the search space by splitting the problem into independent sub-problems in a divide-and-conquer fashion. Let us suppose that at a certain step of our computation there exists a value j P ttrJ s : t P Gru for which for each pair of con icting pending edges pt; t1q and pt; t1q we have that either all t; t1; t, and t1 belong to j-group or all t; t1; t, and t1 do not belong to jgroup (such condition is veri ed by sub-procedure GroupIndependent? reported in Figure 6.). Let Gr tt : trJ s ju, if every edge involving tuples in j-group is not con icting with every edge that may be introduced outside j-group then we can split the problem into the two sub-problems pGr; k; Gr X Gr; Gr X Grq and pGrzGr; k; Gr zGr; Gr zGrq. Such problems are independent and may be resolved in a separate way. The resulting value for the solution is the sum of the values returned by T upleW iseM in applied to both the two sub-problems. Let H |Gr zpGr Y Gr q| and h |tt P pGr zpGr Y Gr qq : trJ s ju|, notice that, in this case, the upper bound of the complexity at the current step of computation drops from Op2H q to Op2H h 2hq.
The second optimization allows us to prune a sub-tree of computation even before a contradiction arises. The second optimization implements a criteria to detect, in many cases, if every possible solution that may be built starting from the current partial one turns to be not minimal. Suppose that there exists an active o-pair pt; t1q in a partial solution pGr; Gr ; Gr q such that there exists t P Gr in the same J -group of t with trV T s trV T s t1rV T s. By de nition of active o-pair, we have that t belongs to Gr as well as every tuple t1 in the same J group of t with trV T s t1rV T s t1rV T s, here the additional condition is that there exists at least one of such tuples. Given a partial solution pGr; Gr ; Gr q we denote with colorspGr; Gr ; Gr q the set colorspGr; Gr ; Gr q tpx; y; zq : there exists an active edge pt; t1q with cpt; t1q px; y; zqu. Let us de ne the set of colors pendingpGr; Gr ; Gr q tpx; y; zq : there exists a pending edge pt; t1q with cpt; t1q px; y; zqu which collects all and only the colors that may be introduced later on in the current computation.
A color px; y; zq is safe in pvt; vt1; jq if and only if one of the following three conditions hold:
2. every color px; y; z1q in pendingpGr; Gr ; Gr q satis es z1 z (i.e., px; y; zq is a pending color and there is no pending color that is con icting with px; y; zq); 3. the color is not con icting with any color in colorspGr; Gr ; Gr q Y pendingp Gr; Gr ; Gr q and do not exist two tuples t; t1 P pGr Y Gr q X tt2 P Gr : t2rJ s j ^ trV T s ¤ t2 ¤ t1rV T su such that pt; t1q is an edge and the color ptrXs; t1rY s; t1rZsq is con icting with px; y; zq Notice that the above three conditions imply that if a color is safe in pvt; vt1; jq then it is neither in con ict with a color colorspGr; Gr ; Gr q nor with a color in pendingpGr; Gr ; Gr q, however this is just a necessary but not su cient condition. Given a partial solution pGr; Gr ; Gr q and the triple pvt; vt1; jq a pvt; vt1; jqreplace DAG is a DAG pV; Eq where V tt P Gr : trV T s vt ^ trJ s ju Y tt P Gr : vt trV T s vt1 ^ trJ s ju Y tt P Gr : trV T s ju and E " pt; t1q P V
V : ptrV T s tpt; t1q P V
vt _ t1rV T s vt1q ^ trV T s t1rV T s^ * cpt; t1q is safe in pvt; vt1; jq
Y vt _ t1rV T s vt1q ^ t1rV T s trV T s ¡ ku
A node t P V is a starting node (resp. ending node) if and only if vt trV T s vt1 and for every t1 P V with t1rV T s vt (resp. t1rV T s vt1) we have pt1; tq P E (resp. pt; t1q P E). A replace path is pvt; vt1; jq-replace DAG pV; Eq is any path t1 : : : tm in pV; Eq for whicht t1 is a starting node and tm is an ending node. We say that vt and vt1 in j can be safely replaced if and only if there exists a replace path in the pvt; vt1; jq-replace DAG pV; Eq.
Using the above de nitions of replace DAGs/paths we can provide the following result.
Theorem 2. Given a partial solution pGr; Gr ; Gr q if there exists a group j with two consecutive valid times vt and vt1 such that vt and vt1 can be safely replaced in j then every consistent solution that follows pGr; Gr ; Gr q is not optimal.
The proof of the theorem is very simple and left as exercise to the reader. Let us suppose that t1 : : : tm is a replace path in the pvt; vt1; jq-replace DAG, it must exists by hypothesis and by de nition we have t1; : : : ; tm P Gr , it sufces to take any consistent solution pGr; Gr ; Gr q that follows pGr; Gr ; Gr q and that pGr; Gr Y tt1; : : : ; tmu; Gr ztt1; : : : ; tmuq is still a consistent solution, non-optimality immediately follows. We take advantage of Theorem 2 by pruning every computation rooted in a partial solution pGr; Gr ; Gr q that features a J -group j-group and two consecutive valid times vt and vt1 in j-group such that vt and vt1 can be safely replaced in j. Notice that verify wether or not such condition applies may be performed in polynomial time. In the procedure T upleW iseM in, this optimization is realized by the joint work of sub-procedures M aximalP aths? and ReplaceP ath? reported in Figure 7 and 6 respectively. 3
In this work we propose an algorithm for solving the problem of verifying whether or not a given APEFD E F holds over a given instance r of a temporal schema. Such problem is known to be NP-Complete in the size of r (i.e., data-complexity). We expect our algrithm to perform considerably better w.r.t. standard branch and bound procedures since it considerably prune the search space in most cases. We are building a prototype in order to measure the e ective improvement w.r.t. frameworks that solve generic NP-Complete problems (i.e., Integer Linear Programmming tools, SAT solvers, and logic programming), obviously this implies that we have to encode our problem in such formalisms.