Abstract:
Methods and apparatus are provided for propagating functional dependencies with conditions. Propagation covers are computed using an SPC view of a dataset, wherein the SPC view comprises selection, projection and Cartesian product operations. Selection operations are processed to extract equivalence classes. Cartesian product operations are processed to obtain a renamed set of the plurality of conditional functional dependencies, that have attributes appearing in the SPC view. Domain constraints from the equivalence classes are applied to the renamed set to remove attributes not in the SPC view. Projection operations are processed using a reduction by resolution procedure to identify inferences that can be propagated to the SPC view from the conditional functional dependencies having attributes that do not appear in the SPC view. Domain constraints of the equivalence classes are converted to conditional functional dependencies; and a minimal cover of the SPC view is determined.

Description:
FIELD OF THE INVENTION 
     The present invention relates to the dependency propagation problem for conditional functional dependencies (CFDs) and, more particularly, to methods and apparatus for computing a propagation cover for conditional functional dependencies. 
     BACKGROUND OF THE INVENTION 
     The World Wide Web makes it possible to exchange and integrate data on an unprecedented scale. A natural question in connection with data exchange and integration concerns whether dependencies that hold on data sources still hold on the target data (i.e., data transformed via mapping from the sources). As dependencies (often referred to as integrity constraints) specify a fundamental part of the semantics of the data, one wants to know whether or not the dependencies are propagated from the sources via the mapping, i.e., whether the mapping preserves information. 
     The dependency propagation problem determines, given a view (mapping) defined on data sources and dependencies that hold on the sources, whether or not another dependency is guaranteed to hold on the view. The dependencies defined on the sources are referred to as source dependencies, and those on the view are referred to as as view dependencies. 
     The dependency propagation problem has been extensively studied when source and view dependencies are functional dependencies (FDs), for views defined in relational algebra. It has been found that while many source FDs may not hold on the view as they are, they do hold on the view under conditions. In other words, source FDs are indeed propagated to the view, not as standard FDs but as FDs with conditions. The FDs with conditions are in the form of conditional functional dependencies (CFDs). See, U.S. patent application Ser. No. 12/411,935, filed Mar. 26, 2009, entitled “Methods and Apparatus for Identifying Conditional Functional Dependencies,” incorporated by reference herein. While the implication and consistency problems for CFDs are addressed, the propagation problem is not considered. 
     A need therefore exists for methods and apparatus for computing a propagation cover for conditional functional dependencies. 
     SUMMARY OF THE INVENTION 
     Generally, methods and apparatus are provided for propagating functional dependencies with conditions. According to one aspect of the invention, propagation covers are computed using an SPC view of a dataset (an SPC view comprises Selection, Projection and Cartesian product operations). The exemplary method comprises the steps of: obtaining a plurality of conditional functional dependencies defined over a schema for the dataset, such as a minimal cover of conditional functional dependencies; processing one or more of the selection operations in the SPC view to extract one or more equivalence classes; processing one or more of the Cartesian product operations in the SPC view to obtain a renamed set of the plurality of conditional functional dependencies, wherein the renamed set comprise conditional functional dependencies having attributes appearing in the SPC view; applying one or more domain constraints from the one or more equivalence classes to the renamed set to remove one or more attributes not in the SPC view; processing one or more of the projection operations in the SPC view using a reduction by resolution procedure to identify one or more inferences that can be propagated to the SPC view from the one or more conditional functional dependencies having attributes that do not appear in the SPC view; converting one or more domain constraints of the equivalence classes to conditional functional dependencies; and determining a cover of the SPC view, such as a minimal cover of the SPC view. 
     According to additional aspects of the invention, a test is performed to determine if two or more of the conditional functional dependencies are inconsistent. If there are one or more inconsistencies in the equivalence classes, at least one set of conflicting conditional functional dependencies is returned. 
     A more complete understanding of the present invention, as well as further features and advantages of the present invention, will be obtained by reference to the following detailed description and drawings. 
    
    
     
       BRIEF DESCRIPTION OF THE DRAWINGS 
         FIG. 1  illustrates three exemplary instances of three data sources containing information about customers in the United Kingdom (UK), United States (US) and the Netherlands, respectively; 
         FIG. 2  is a sample table illustrating the complexity of CFD propagation for various view languages; 
         FIG. 3  provides exemplary pseudo code for an exemplary embodiment of the algorithm incorporating features of the present invention; 
         FIG. 4  provides exemplary pseudo code for an exemplary embodiment of a reduction by resolution (RBR) procedure; 
         FIG. 5  provides exemplary pseudo code for an exemplary embodiment of an EQ2CFD procedure incorporating features of the present invention; and 
         FIG. 6  is a block diagram of a CFD Propagation Cover Computation System that can implement the processes of the present invention. 
     
    
    
     DETAILED DESCRIPTION 
     The present invention provides methods and apparatus for computing a propagation cover. The disclosed algorithms determine whether a given view dependency is propagated from source dependencies, and find a cover of all view dependencies propagated via SPC views. For a more detailed discussion of the complexity and experimental results of the algorithms described herein, see, W. Fan et al., “Propagating Functional Dependencies with Conditions,” Proc. of Very Large Data Bases (VLDB) &#39;08 (August 2008), incorporated by reference herein. 
     Example 1.1 
     Consider three data sources R 1 , R 2  and R 3 , containing information about customers in the United Kingdom (UK), United States (US) and the Netherlands, respectively. It is assumed that these data sources have a uniform schema:
         R i  (AC: string, phn: string, name: string, street: string, city: string, zip: string)
 
Each tuple in an R i  relation specifies a customer&#39;s information (area code (AC), phone number (phn), name and address (street, city, zip code)), for i∈[1,3]. Example instances D 1 , D 2  and D 3  of R 1 , R 2  and R 3  are shown in  FIG. 1 .
       

     Consider the following FDs defined on the UK and Netherland sources: in instances of R i , zipcode uniquely determines street (f 1 ), and area code uniquely determines city (f 2 ); moreover, area code determines city in R 3  data (f 3 )
         f 1 : R 1 (zip→street), f 2 : R 1 (AC→city), f 3 : R 3 (AC→city).       

     Define a view V with query Q 1 ∪Q 2 ∪Q 3  to integrate the data from the three sources, where Q 1  is 
     select AC, phn, name, street, city, zip, ‘44’ as CC from R 1    
     Define Q 2  and Q 3  by substituting ‘01’ and ‘31’ for ‘44’, R 2  and R 3  for R 1  in Q 1 , respectively. The target schema R has all the attributes in the sources and a country-code attribute CC (44, 01, 31 for the UK, US and Netherlands, respectively). 
     As shown in  FIG. 1 , f 1  on the R 1  source does not hold on the target data (view). The view violates f 1  due to tuples t 3 , t 4  extracted from D 2 . Indeed, in the US, zip does not determine street. In other words, f 1  is not propagated to the view as an FD. In contrast, the following CFD holds on the view:
         φ 1 : R([CC=‘44’, zip]→[street]).
 
That is, for UK customers in the view, zipcode uniquely determines street. In other words, φ 1  is an “FD” with a condition: it is to hold only on the subset of tuples in the view that satisfies the pattern CC=‘44,’ rather than on the entire view. It cannot be expressed as a standard FD.
       

     Similarly, from f 2  and f 3  one cannot derive a standard FD on the view to assert that “area code uniquely determines city.” Indeed, from tuples t 1  and t 5  in  FIG. 1 , it can be seen that 20 is an area code in both the UK and the Netherlands, for London and Amsterdam, respectively. However, the following CFDs can be propagated from f 2  and f 3  via the view:
         φ 2 : R([CC=‘44’, AC]→[city]),   φ 3 : R([CC=‘31’, AC]→[city]).       

     That is, f 2  and f 3  hold conditionally on the view: area code determines city for tuples with CC=‘44’ (φ 2 ) or CC=‘31’ (φ 3 ). In other words, the semantics specified by the FDs on the sources is preserved by the CFDs on the view. 
     Furthermore, given the following CFDs on the sources:
         cfd 1 : R 1 ([AC=‘20’]→[city−‘ldn’]),   cfd 2 : R 3 ([AC=‘20’]→[city=‘Amsterdam’]),
 
then the following CFDs are propagated to the view:
       

     φ 4 : R([CC=‘44,’ AC=‘20’]→[city=‘ldn’]), 
     φ 5 : R([CC=‘31,’ AC=‘20’]→[city=‘Amsterdam’]), 
     which carry patterns of semantically related constants. 
     It is submitted that no previous algorithms developed for FD propagation are capable of deriving these CFDs from the given source FDs via the view. This highlights the need for investigating dependency propagation, for CFDs as view dependencies. 
     The present invention can be employed in a number of exemplary applications: 
     (1) Data Exchange. Recall Example 1.1. Suppose that the target schema R and CFDs φ 2  and φ 3  are predefined. Then, the propagation analysis assures that the view definition V is a schema mapping from (R 1 , R 2 , R 3 ) to R, i.e., for any source instances D 1  and D 3  of R 1  and R 3  that satisfy the FDs f 2  and f 3 , respectively, and for any source instance D 2  of R 2 , the view V(D 1 , D 2 , D 3 ) is an instance of the target schema R and is guaranteed to satisfy φ 2  and φ 3 . 
     (2) Data Integration. Suppose that V is a mapping in an integration system, which defines a global view of the sources. Then, certain view updates, e.g., insertion of a tuple t with CC=‘44,’ AC=‘20’ and city=‘edi,’ can be rejected without checking the data, since it violates the CFD φ 4  propagated from the sources. 
     (3) Data Cleaning. In contrast to FDs that were developed for schema design, CFDs have been proposed for data cleaning. Suppose that CFDs φ 1 -φ 5  are defined on the target database, for checking the consistency of the data. Then, propagation analysis assures that one need not validate these CFDs against the view V. In contrast, if in addition, an FD φ 6 : R(CC, AC, phn→street, city, zip) is also defined on the target, then φ 6  has to be validated against the view since it is not propagated from the source dependencies. 
     Views are generally expressed in various fragments of relational algebra (RA), and source dependencies are generally expressed either as traditional FDs or CFDs. It has been found that in many cases CFD propagation retains the same complexity as its FD counterpart, but in some cases CFDs do incur extra complexity. The dependency propagation problem is considered in the presence of finite-domain attributes. 
     According to one aspect of the present invention, algorithms are provided for computing a propagation cover. In many applications, one wants not only to know whether a given view dependency is propagated from source dependencies, but also to find a cover of all view dependencies propagated. From the cover, all view dependencies can be deduced via implication analysis. This is needed for, e.g., processing view updates and detecting inconsistencies, as shown by the data integration and data cleaning examples given above. 
     Even for certain FDs and views defined with a single projection operator, a minimal cover of all view FDs propagated is sometimes necessarily exponentially large, in the infinite-domain setting. A typical method to find a cover is by first computing the closure of all source FDs, and then projecting the closure onto the view schema. While this method always takes exponential time, it is the algorithm recommended by database textbooks. 
     Already hard for FDs and projection views, the propagation cover problem is intriguing for CFDs and SPC views. The present invention provides an algorithm to compute a minimal cover of CFDs propagated via SPC views in the absence of finite-domain attributes, by extending a practical algorithm proposed in S. Gottlob, “Computing Covers for Embedded Functional Dependencies,” Proc. of Principles of Database Systems (PODS) (1987), incorporated by reference herein and hereinafter referred to as Gottlob 1987, for computing a cover of FDs propagated via projection views. Despite the increased expressive power of CFDs and SPC views, the disclosed algorithm has approximately the same complexity as the algorithm of Gottlob 1987. The disclosed algorithm behaves polynomially in many practical cases. Indeed, exponentially large covers are mostly found in examples intentionally constructed. Further, from this algorithm, an effective polynomial-time heuristic is immediate: it computes a minimal cover when the cover is not large, and returns a subset of a cover as soon as the computation reaches a predefined bound, when covers are inherently large. 
     The present invention thus computes minimal propagation covers via SPC views, for FDs or CFDs. 
     Dependencies and Views 
     Conditional Functional Dependencies 
     CFDs extend FDs by incorporating a pattern tuple of semantically related data values. For each attribute A in a schema R, its associated domain is denoted as dom(A), which is either infinite (e.g., string, real) or finite (e.g., Boolean, date). 
     Definition 2.1: A CFD φ on a relation schema R is a pair R (X→Y, t p ), where (1) X→Y is a standard FD, called the FD embedded in φ; and (2) t p  is a tuple with attributes in X and Y, referred to as the pattern tuple of φ, where for each A in X (or Y), t p [A] is either a constant ‘a’ in dom(A), or an unnamed variable ‘_’ that draws values from dom(A). The X and Y attributes in t p  are separated with ‘∥’. 
     For CFDs on views (i.e., view CFDs) a special form R(A→B,(x∥x)) is allowed, where A, B are attributes of R and x is a (special) variable. 
     Note that traditional FDs are a special case of CFDs, in which the pattern tuples consist of ‘_’ only. 
     Example 2.1 
     The dependencies discussed above can be expressed as CFDs, such as: 
     φ 1 : R([CC, zip]→[street], (44, _∥_)), 
     φ 2 : R([CC, AC]→[city], (44, _∥_)), 
     φ 4 : R([CC, AC]→[city], (44, 20∥ldn)), 
     f 1 : R 1 (zip→street, (_∥_)). 
     The standard FD f 1  on source R 1  is expressed as a CFD. 
     The semantics of CFDs is defined in terms of a relation             on constants and ‘_’: η 1           η 2  if either η 1 =η 2 , or one of η 1 ,η 2  is ‘_’. The operator           naturally extends to tuples, e.g., (Portland, LDN)         (_, LDN) but (Portland, LDN)         (_, NYC). A tuple t 1  matches t 2  if t 1           t 2 .
     An instance D of R satisfies φ=R(X→Y, t p ), denoted by D|=φ, if for each pair of tuples t 1 ,t 2  in D, if t 1 [X]=t 2 [X]           t p [X], then t 1 [Y]         t p [Y].
     Intuitively, φ is a constraint defined on the set D φ ={t|t∈D,t[X]           t p [X]} such that for any t 1 ,t 2 ∈D φ , if t 1 [X]=t 2 [X], then (a) t 1 [Y]=t 2 [Y], and (b) t 1 [Y]         t p [Y]. Here, (a) enforces the semantics of the embedded FD, and (b) assures the binding between constants in t p [Y] and constants in t 1 [Y]. Note that φ is defined on the subset D φ  of D identified by t p [X], rather than on the entire D.
     An instance D of R satisfies CFD R(A→B,(x∥x)) if for any tuple t in D, t[A]=t[B]. As discussed further below, these CFDs are used to express selection conditions of the form A=B in a view definition, treating domain constraints and CFDs in a uniform framework. 
     An instance D of a relational schema R satisfies a set Σ of CFDs defined on R, denoted by D|=Σ, if D|=φ for each φ in Σ. 
     Example 2.2 
     Recall the view definition V from Example 1.1, and the instances D 1 ,D 2 ,D 3  of  FIG. 1 . The view V(D 1 ,D 2 ,D 3 ) satisfies φ 1 , φ 2 , φ 4  of Example 2.1. However, if attribute CC are removed from φ 4 , then the view no longer satisfies the modified CFD. Indeed, there are two tuples t 1′  and t 5′  in V(D 1 ,D 2 ,D 3 ) such that t 1′  and t 1  of  FIG. 1  have identical AC and city values; similarly for t 5  and t 5′  of  FIG. 1 . Then, t 1′  and t 5′  violate the modified CFD: they have the same AC attribute but differ in city. 
     View Definitions 
     The present invention addresses dependency propagation for views expressed in various fragments of RA. The problem is already undecidable for FDs and views defined in RA. Consider a relational schema R=(S 1 , . . . , S m ). 
     SPC. An SPC query (also referred to as a conjunctive query) Q on R is an RA expression defined in terms of the selection (σ), projection (π), Cartesian product (×) and renaming (ρ) operators. It can be expressed in the following normal form:
 
π Y ( R   c   ×E   s ), where  E   s =σ F ( E   c ),  E   c   =R   1   × . . . ×R   n ,
 
where (a) R c ={(A 1 :a 1 , . . . , A m :a m )}, a constant relation, such that for each i∈[1,m], A i  is in Y, A i &#39;s are distinct, and a i  is a constant in dom(A i ); (b) for each j∈[1,n], R j  is ρ j (S) for some relation atom in R, and ρ j  is a renaming operator such that the attributes in R j  and R l  are disjoint if j≠l, and A i  does not appear in any R j ; (c) F is a conjunction of equality atoms of the form A=B and A=‘a’ for a constant a∈dom(A).
 
     Fragments of SPC are also considered, denoted by listing the operators supported: S, P, C, SP, SC, and PC (the renaming operator is included in all these subclasses by default without listing it explicitly). For instance, SC is the class of queries defined with σ, × and ρ operators. 
       FIG. 2  is a sample table  200  illustrating the complexity of CFD propagation for various view languages. 
     For example, Q 1  given in Example 1.1 can be expressed as a C query: (CC: 44)×R 1 . 
     SPCU. SPCU (also referred to as a union of conjunctive queries) is an extension of SPC by allowing union (∪). An SPCU query defined on R can be expressed in normal form V 1  ∪ . . . ∪ V n , where V i &#39;s are union-compatible SPC queries. For example, the view V given in Example 1.1 is an SPCU query. 
     Computing Covers of View Dependencies 
     As indicated above, the present invention provides methods and apparatus for computing a propagation cover. The disclosed algorithms determine whether a given view dependency is propagated from source dependencies, and find a cover of all view dependencies propagated. In other words, aspects of the present invention find a minimal cover of all view CFDs propagated from source CFDs. 
     The disclosed exemplary algorithm for finding a propagation cover also readily provides a solution for determining whether a given CFD φ is propagated from a given set Σ of source CFDs via an SPC view V: one can compute a minimal cover Γ of all CFDs propagated from Σ via V, and then check whether Γ implies φ. 
     The disclosed exemplary algorithm for finding a propagation cover is an extension of a practical algorithm proposed in Gottlob 1987, for computing covers of FDs propagated via projection views. The disclosed exemplary algorithm has the same complexity as that of Gottlob 1987, and behaves polynomially in many practical cases. The disclosed exemplary algorithm also yields an algorithm for computing propagation covers when FDs are source dependencies, a special case. 
     The absence of finite-domain attributes is assumed, the same setting as the classical work on FD propagation. In this setting, the emptiness problem for CFDs and SPC views, and the CFD propagation problem via SPC views are all in ptime. Without loss of generality, CFDs are considered in the normal form: (R: X→A,t p ), where A is a single attribute. Indeed, each CFD of the general form given int the section entitled “Dependences and Views,” can be converted in linear time to an equivalent set of CFDs in the normal form. 
     Propagation Cover Problem 
     Implication and Cover. A set Σ of CFDs defined on a schema R implies another CFD φ on R, denoted by Σ|=φ, if for any instance D of R, if D|=Σ then D|=φ. 
     A cover of a set Σ of CFDs is a subset Σ c  of Σ such that for each CFD φ in Σ, Σ c |=φ. In other words, Σ c  is contained in, and is equivalent to, Σ. For example, recall the notion of the closure F +  of a set F of FDs, which is needed for designing normal forms of relational schema. Then, F is a cover of F + . 
     A minimal cover Σ mc  of Σ is a cover of Σ such that
         no proper subset of Σ mc  is a cover of Σ, and   for each CFD φ=R(X→A, t p ) in Σ mc , there exists no proper subset Z⊂X such that (Σ mc ∪{φ′})−{φ}|=φ, where φ′=R(Z→A,(t p [Z]∥t p [A])).       

     That is, there is neither redundant attributes in each CFD nor redundant CFDs in Σ mc . 
     Only nontrivial CFDs are included in Σ mc . A CFD R(X→A, t p ) is nontrivial if either (a) A∉X, or (b) X=AZ but t p  is not of the form (η 1 ,  d Z   ∥η 2 ), where either η 1 =η 2 , or η 1  is a constant and η 2 =‘_’. 
     It is known that without finite-domain attributes, implication of CFDs can be decided in quadratic time. Further, there is an algorithm referred to as MinCover that computes Σ mc  in O(|Σ| 3 ) time for any given set Σ of CFDs. See, U.S. patent application Ser. No. 12/411,935, filed Mar. 26, 2009, entitled “Methods and Apparatus for Identifying Conditional Functional Dependencies,” incorporated by reference herein. 
     Propagation Cover. For a view V defined on a schema R and a set Σ of source CFDs on R, CFD p (Σ,V) denotes the set of all view CFDs propagated from Σ via V. 
     The propagation cover problem is to compute, given V and Σ, a cover Γ of CFD p (Σ,V). Γ is referred to as a propagation cover of Σ via V, and as a minimal propagation cover if Γ is a minimal cover of CFD p (Σ,V). 
     Challenges. The following example shows that the problem is already hard for FDs and P views. 
     Example 3.1 
     Consider a schema R with attributes A i , B i , C i  and D, and a set Σ of FDs on R consisting of A i →C i , B i →C i , and C 1 , . . . , C n →D, for each i∈[1,n]. Consider a view that projects an R relation onto their A i ,B i  and D attributes, dropping C i &#39;s. Then, any cover Σ c  of the set of view FDs propagated necessarily contains all FDs of the form η 1 , . . . , η n →D, where η i  is either A i  or B i  for i∈[1,n]. Σ c  contains at least 2 n  FDs, whereas the size of the input, namely, Σ and the view, is O(n). Indeed, to derive view FDs from C 1 , . . . , C n →D, one can substitute either A i  or B i  for each C i , leading to an exponential blowup. 
     In contrast, the dependency propagation problem is in ptime in this setting (See, e.g.,  FIG. 2 ). This shows the sharp distinction between the dependency propagation problem and the propagation cover problem. 
     The computation of embedded FDs computes a propagation cover of FDs via projection views. Given a schema R, a set F of FDs on R and a set Y of attributes in R, it is to find a cover F c  of all FDs propagated from F via a projection view π Y (R). An algorithm for finding F c  is by first computing the closure F +  of F, and then projecting F +  onto Y, removing those FDs with attributes not in Y. This algorithm takes O(2 |F| ) time, for computing F + . 
     The propagation cover problem is more intricate for CFDs and SPC views. 
     (a) While at most exponentially many FDs can be defined on a schema R, there are possibly infinitely many CFDs. Indeed, there are infinitely many CFDs of the form R(A→B,t p ) when t p [A] ranges over values from an infinite dom(A). 
     (b) While AX→A is a trivial FD and can be ignored, φ=R(AX→A,t p ) may not be ignored. Indeed, when t p  is (_,  d X   ∥a). φ is meaningful: it asserts that for all tuples t such that t[X]             d X   , the A column has the same constant ‘a’.
     (c) While X→Y and Y→Z yield X→Z for FDs, the transitivity rule for CFDs has to take pattern tuples into account and is more involved than its FD counterpart. 
     (d) Selection and Cartesian product introduce interaction between domain constraints and CFDs, a complication of SPC views not encountered when dealing with projection views. 
     Propagating CFDs Via SPC Views 
     The exponential complexity of Example 3.1 is for the worst case and is only found in examples intentionally constructed. In practice, it is common to find a propagation cover of polynomial size, and thus it may be an overkill to use algorithms that always take exponential time. Thus, an algorithm is needed for computing minimal propagation covers that behaves polynomially most of the time, whereas it necessarily takes exponential time only when all propagation covers are exponentially large for a given input. The present invention provides an algorithm, referred to as PropCFD SPC, that extends the algorithm of Gottlob 1987 for computing a propagation cover of FDs via projection views. Given an SPC view V defined on a schema R, and a set Σ of source CFDs on R, the disclosed PropCFD SPC computes a minimal propagation cover Γ of Σ via V, without increasing the complexity of the extended algorithm, although CFDs and SPC views are more involved than FDs and P views, respectively. 
     Before PropCFD SPC is presented, some basic results are provided. Let R=(S 1 , . . . , S m ) be the source schema. Recall from the section entitled “Dependencies and Views” that V defined on R is of the form:
 
π Y ( R   c   ×E   s ),  E   s =σ F ( E   c ),  E   c   =R   1   × . . . ×R   n  
 
where R c  is a constant relation, R j &#39;s are renamed relation atoms ρ j (S) for S in R, Y is the set of projection attributes, and F is a conjunction of equality atoms.
 
     Basic Results. The constant relation R c  introduces no difficulties: for each (A i :a i ) in R c , a CFD R V (A i →A i ,(_∥a)) is included in Γ, where R V  is the view schema derived from V and R. Thus, it is assumed that V=π Y (E s ). 
     The reduction below allows a focus on E s  instead of V. 
     Proposition 3.1: For any SPC view V of the form above, and any set Σ of source CFDs, Σ|= V φ iff Σ|= E     s   φ when
         φ=R V (A→B,(x∥x)), denoting A=B;   φ=R V (A→A,(_∥a)), denoting A=‘a’; or   φ=R V (X→A,t p );
 
where A∈Y, B∈Y, and X ⊂ Y.
       

     Consider the interaction between CFDs and operators ×,σ and π in the view definition V. 
     Cartesian Product. Observe that each R j  in E c  is ρ j (S), where S is in R. All source CFDs on S are propagated to the view, after their attributes are renamed via ρ j . 
     Selection. The condition F in σ F  brings domain constraints into play, which can be expressed as CFDs. 
     Lemma 3.2: (a) If A=‘a’ is in the selection condition F, then R V (A→A,(_∥a)) is in CFD p (Σ,V). (b) If A=B is in F, then R V (A→B,(x∥x)) is in CFD p (Σ,V) for the special variable x. 
     That is, one can incorporate domain constraints A=‘a’ and A=B enforced by the view V into CFDs. Here (a) asserts that the A column of the view contains the same constant ‘a’, and (b) asserts that for each tuple t in the view, t[A] and t[B] are identical, as required by the selection condition F in the view V (this is why CFDs of the form R V (A→B,(x∥x)) were introduced in the section entitled “Dependencies and Views”). 
     Lemma 3.3: If R V (A→B,(x∥x)) and R V (BX→G,t p ), then R V (AX→G,t p′ ) is in CFD p (Σ,V), where t p′ [A]=t p [B], t p′ [X]=t p [X] and t p′ [G]=t p [G]. 
     That is, view CFDs can be derived by applying the domain constraint A=B: substituting A for B in a view CFD yields another view CFD. This also demonstrates how domain constraints interact with CFD propagation. 
     Σ d  denotes these CFDs as well as those in Σ expressing domain constraints. Based on Σ d , it can be decided whether A=B or A=‘a’ for attributes in Y (i.e., R V ). 
     More specifically, the attributes are partitioned into a set EQ of equivalence classes, such that for any eq∈EQ, and for any attributes A,B in Y, (a) A, B∈eq iff A=B can be derived from Σ d ; (b) if A=‘a’ can be derived from Σ d  and moreover, A∈eq, then for any B∈eq, B=‘a’; the constant ‘a’ as is key of eq, denoted by key(eq). If a constant is not available, key(eq) is ‘_’. 
     The use of EQ helps decide whether or not V and Σ always yield empty views, which happens if there exists some eq∈EQ such that key(eq) is not well-defined, i.e., when two distinct constants are associated with eq. 
     A procedure is provided to compute EQ, referred to as ComputeEQ, which takes Σ and V as input, and returns EQ as output, along with key(eq) for each eq∈EQ. If key(eq) is not well-defined for some eq, it returns a special symbol ‘           ’, indicating the inconsistency in V and Σ.
     Projection. To remedy the limitations of closure-based methods for computing propagation covers of FDs via P views, Gottlob 1987 proposed a practical algorithm based on the idea of Reduction by Resolution (RBR). RBR and the algorithm of Gottlob 1987 are extended herein to handle CFDs and projection. 
     To illustrate RBR, a partial order ≦ is we first defined on constants and ‘_’: η 1 ≦η 2  if either η 1  and η 2  are the same constant ‘a’, η 2 =‘_’. 
     Given CFDs φ 1 =R(X→A,t p ) and φ 2 =R(AZ→B,t p′ ), if t p [A]≦t p′ [A] and for each C∈X∩Z, t p [C]           t p′ [C], then φ=R(XZ→B,s p ) can be derived based on CFD implication (See, U.S. patent application Ser. No. 12/411,935, referenced above). Here, s p =(t p [X]⊕t p′ [Z]∥t p′ [B]), and t p [X]⊕t p′ [Z] are defined as follows:
       for each C∈X−Z, s p [C]=t p [C];   for each C∈Z−X, s p [C]=t p′ [C];   for each C∈X ∩ Z, s p [C]=min(t p [C],t p′ [C]), i.e., the smaller one of t p [C] and t p′ [C] if either t p [C]≦t p′ [C] or t p′ [C]≦t p [C]; it is undefined otherwise.       

     Following Gottlob 1987, φ is referred to as an A-resolvent of φ 1  and φ 2 . 
     Example 3.2 
     Consider CFDs φ=R([A 1 ,A 2 ]→A,t 1 ) and φ 2 =R([A,A 2 ,B 1 ]→B,t 2 ), where t 1 =(_,c∥a) and t 2 =(_,c,b∥_). Then, φ=R([A 1 ,A 2 ,B 1 ]→B,t p ) is an A-resolvent of φ 1  and φ 2 , where t p =(_,c,b∥_). 
     Following Gottlob 1987, the following are defined. Given π Y  (R) and a set Σ of CFDs on R, let U be the set of attributes in R.
         For A∈(U−Y), let Res(Σ,A) denote the set of all nontrivial A-resolvents. Intuitively, it shortcuts all CFDs involving A.   Denote by Drop(Σ,A) the set Res(Σ,A)∪Σ[U−{A}], where Σ[Z] denotes the subset of Σ by including only CFDs with attributes in Z.   Define RBR(Σ, A)=Drop(Σ, A) and inductively, RBR(Σ, A)=Drop(Drop(Σ,A),Z).       

     Then, the following result is provided, in which F +  denotes the closure of F, i.e., the set of all CFDs implied by F. 
     Proposition 3.4: For a view π Y (R) and a set Σ of CFDs on R, (a) for each A∈(U−Y), Drop(Σ, A) + =Σ + [U−{A}]; (b) RBR(Σ, U−Y) is a propagation cover of Σ via π Y (R), where U is the set of attributes in R. 
     A procedure is provided for computing a propagation cover of Σ via π Y (R), also denoted by RBR. Generally, the idea is to repeatedly “drop” attributes in U−Y, shortcutting all CFDs that involve attributes in U−Y. The procedure takes as input Σ and π Y (R), and returns RBR(Σ,U−Y) as the output. 
     Lemma 3.5: If for any source instance D where D|=Σ, V(D) is empty, then R V (A→A,(_∥a)) and R V (A→A,(_∥b)) are in CFD p (Σ,V), for any attribute A in R V  and any distinct values a, b∈dom(A). 
     Generally, this ensures that the view is always empty (based on the emptiness problem): no tuple t in the view can possibly satisfy the CFDs, which require t[A] to take distinct a and b as its value. As a result, any CFD on the view can be derived from these “inconsistent” CFDs. 
     Algorithm for Computing Minimal Covers 
       FIG. 3  provides exemplary pseudo code for an exemplary embodiment of the algorithm PropCFD_SPC  300 . As shown in  FIG. 3 , the algorithm  300  first processes selection σ F  (line  2 ), extracting equivalence classes EQ via procedure ComputeEQ, described above (not shown). If an inconsistency is discovered, algorithm  300  returns a pair of “conflicting” view CFDs that ensure the view is empty (lines  3 - 4 ). Algorithm  300  then processes the Cartesian product, and gets a set Σ V  of CFDs via renaming as described above (lines  5 - 6 ). Algorithm  300  applies the domain constraints of EQ to Σ V  (line  9 ), by designating an attribute rep(eq) for each equivalence class eq in EQ (line  8 ), which is used uniformly wherever attributes in eq appear in CFDs of Σ V . Algorithm  300  also removes attributes in eq that are not in the projection list Y (line  10 ), since these attributes do not contribute to view CFDs. Next, algorithm  300  handles the projection π Y , by invoking procedure RBR (line  11 ), discussed below in conjunction with  FIG. 4 , and then converts domain constraints of EQ to CFDs via procedure EQ2CFD (line  12 ), discussed below in conjunction with  FIG. 5 . Finally, algorithm  300  returns a minimal cover of the results returned by these procedures, by invoking procedure MinCover, referenced above. This yields a minimal propagation cover of V via Σ (line  13 ). 
       FIG. 4  provides exemplary pseudo code for an exemplary embodiment of the RBR procedure  400 . Generally, the RBR procedure  400  implements the RBR method: for each A∈U−Y, the RBR procedure  400  computes an A-resolvent (lines  4 - 8 ) and Drop(Σ, A) (lines  4 - 11 ). Only nontrivial CFDs are included (line  8 ). By dropping all attributes in U−Y, it obtains RBR(Σ, U−Y), a cover of Σ and π Y  by Proposition 3.4, 
       FIG. 5  provides exemplary pseudo code for an exemplary embodiment of the EQ2CFD procedure  500 . Generally, the EQ2CFD procedure  500  converts domain constraints enforced by EQ to equivalent CFDs (lines  2 - 8 ), by Lemma 3.2. For each eq in EQ, the EQ2CFD procedure  500  leverages the constant key(eq) whenever it is available (lines  4 - 5 ). When it is not available, the EQ2CFD procedure  500  uses the special variable x in the CFDs (lines  6 - 8 ). 
     Example 3.3 
     Consider sources R 1 (B 1′ ,B 2 ), R 2 (A 1 ,A 2 ,A), R 3 (A′,A 2′ ,B 1 ,B), and view V=π Y (σ F (R 1 ×R 2 ×R 3 )), where Y={B 1 ,B 2 ,B 1′ ,A 1 ,A 2 ,B}, and F is (B 1 =B 1′  and A=A′ and A 2 =A 2′ ). Consider Σ consisting of ψ 1 =R 2 ([A 1 ,A 2 ]→A,t 1 ) and ψ 2 =R 3 ([A′,A 2 ,B 1 ]→B,t 2 ), for t 1 ,t 2  given in Example 3.2. 
     Applying algorithm PropCFD_SPC  300  to Σ and V, after step  10 , EQ consists of {{B 1 ,B 1′ },{B 2 },{A 1 },{A 2 },{B}}, and Σ V  consists of φ 1 ,φ 2  of Example 3.2. As also given there, procedure RBR returns φ of Example 3.2. The EQ2CFD procedure  500  returns φ′=R(B 1 →B 1′ ,(x∥x)), where R is the view schema with attributes in Y. Then, the cover returned by the algorithm consists of φ and φ′. 
     Analysis. It can be shown that for each φ in CFD p (Σ,V), Γ|=φ, and vice versa, where Γ is the output of the algorithm. 
     For the complexity, let V=π Y (σ F (E c )). Then |Y|≦|E c | and |F|≦(|E c | 2 +|E c |). (a) Procedure ComputeEQ  500  takes O(|E c | 4 *|Σ|) time. (b) EQ2CFD  300  is in O(|Y| 3 ) time. (c) Procedure RBR  400  has the same complexity as its counterpart in Gottlob 1987: O(|E c | 2 *a 3 ), where a is an upper bound for the cardinality of Γ during the execution of RBR  400 . (d) The rest of the computation takes at most O(|Σ| 3 +a 3 +|E c | 2 ) time. Since a is no less than |E c |*|Σ|, RBR  400  takes at least O(|E c | 5 *|Σ| 3 ) time. Putting these together, the cost of RBR  400  dominates. That is, the complexity of PropCFD_SPC  300  is the same as the bound on the algorithm of Gottlob 1987. Note that both Σ and V are defined at the schema level (it has nothing to do with the instances of source databases), and are often small in practice. 
     In one exemplary embodiment, minimal cover is used as an optimization technique. First, Σ is “simplified” by invoking MinCover(Σ) (line  1  of  FIG. 3 ), removing redundant source CFDs. Second (not shown), in procedure RBR  400 , to reduce the size of intermediate Γ during the computation, one can change line  11  of  FIG. 4  to “Γ:=MinCover(Γ∪C)”. In the exemplary implementation, Γ is partitioned into Γ 1 , . . . Γ k , each of a fixed size k 0 , and MinCover(Γ i ) is invoked. This removes redundant CFDs from Γ, to an extent, without increasing the worst-case complexity since it takes O(|Γ|*k 0   2 ) time to conduct. 
     As another optimization technique, one may optionally simplify or minimize input SPC views. This works to an extent: the minimization problem for SPC queries is intractable. 
     System and Article of Manufacture Details 
       FIG. 6  is a block diagram of a CFD Propagation Cover Computation System  600  that can implement the processes of the present invention. As shown in  FIG. 6 , memory  630  configures the processor  620  to implement the methods, steps, and functions disclosed herein (collectively, shown as CFD propagation cover computation processes  680  in  FIG. 6 ). The memory  630  could be distributed or local and the processor  620  could be distributed or singular. The memory  630  could be implemented as an electrical, magnetic or optical memory, or any combination of these or other types of storage devices. It should be noted that each distributed processor that makes up processor  620  generally contains its own addressable memory space. It should also be noted that some or all of computer system  600  can be incorporated into a personal computer, laptop computer, handheld computing device, application-specific circuit or general-use integrated circuit. 
     As is known in the art, the methods and apparatus discussed herein may be distributed as an article of manufacture that itself comprises a computer readable medium having computer readable code means embodied thereon. The computer readable program code means is operable, in conjunction with a computer system, to carry out all or some of the steps to perform the methods or create the apparatuses discussed herein. The computer readable medium may be a recordable medium (e.g., floppy disks, hard drives, compact disks, memory cards, semiconductor devices, chips, application specific integrated circuits (ASICs)) or may be a transmission medium (e.g., a network comprising fiber-optics, the world-wide web, cables, or a wireless channel using time-division multiple access, code-division multiple access, or other radio-frequency channel). Any medium known or developed that can store information suitable for use with a computer system may be used. The computer-readable code means is any mechanism for allowing a computer to read instructions and data, such as magnetic variations on a magnetic media or height variations on the surface of a compact disk. 
     The computer systems and servers described herein each contain a memory that will configure associated processors to implement the methods, steps, and functions disclosed herein. The memories could be distributed or local and the processors could be distributed or singular. The memories could be implemented as an electrical, magnetic or optical memory, or any combination of these or other types of storage devices. Moreover, the term “memory” should be construed broadly enough to encompass any information able to be read from or written to an address in the addressable space accessed by an associated processor. With this definition, information on a network is still within a memory because the associated processor can retrieve the information from the network. 
     It is to be understood that the embodiments and variations shown and described herein are merely illustrative of the principles of this invention and that various modifications may be implemented by those skilled in the art without departing from the scope and spirit of the invention.