METHOD AND SYSTEM FOR CLEANSING SEQUENCE-BASED DATA AT QUERY TIME

• US 20080114744A1
• Filed: 11/14/2006
• Published: 05/15/2008
• Est. Priority Date: 11/14/2006
• Status: Active Grant

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rao, Jun, Doraiswamy, Sangeeta T., Colby, Latha Sankar, Thakkar, Hetal
• Granted Patent: US 7,516,128 B2
• Time in Patent Office: Days
• US Class Current: 707/4
• CPC Class Codes: G06F 16/24534 Query rewriting; Transformation
• CPC Class Codes: Y10S 707/99931 Database or file accessing
• CPC Class Codes: Y10S 707/99933 Query processing, i.e. searching
• CPC Class Codes: Y10S 707/99934 Query formulation, input preparation, or translation
• CPC Class Codes: Y10S 707/99945 Object-oriented database structure processing

Abstract

A method and system for cleansing anomalies from sequence-based data at query time. Sequence-based data such as RFID data is loaded into a database. One or more cleansing rules are received at a cleansing rules engine. The cleansing rule engine converts the cleansing rule(s) to a template that includes logic to compensate for anomalies in the sequence-based data. A query to retrieve the sequence-based data is received by a query rewrite engine. The query rewrite engine rewrites the query by applying the template logic. The rewritten query is executed at query time. The result of the rewritten query execution is identical to the result of executing the original query on a data set generated by applying the cleansing rule to all of the sequence-based data.

Claims

1. A computer-implemented method of cleansing anomalies from sequence-based data at query time, comprising:

loading sequence-based data into a database managed by a database management system (DBMS) of a computing system, said loading being performed at a load time of said sequence-based data that precedes a query time of said sequence-based data;

receiving a cleansing rule at a cleansing rules engine of said computing system;

automatically converting, by said cleansing rules engine, said cleansing rule to a template, said template including logic to compensate for one or more anomalies in said sequence-based data;

receiving, at said query time and by a query rewrite engine of said computing system, a user query to retrieve said sequence-based data;

automatically rewriting, at said query time and by said query rewrite engine, said user query to provide a rewritten query, said automatically rewriting including applying said logic included in said template to compensate for said one or more anomalies; and

executing, at said query time, said rewritten query by said DBMS, wherein an answer provided by said executing said rewritten query is identical to a result of executing said user query on a set of data generated by an application of said cleansing rule to all of said sequence-based data.

2. The method of claim 1, wherein said automatically converting said cleansing rule comprises:

converting a singleton of two singletons to one or more scalar aggregates over a window of size one, wherein said two singletons are two rows of said sequence-based data referred to by a condition of said cleansing rule, wherein said window is defined according to relative sequence positions of said two singletons, and wherein said one or more scalar aggregates and said window are specified in SQL/OLAP.

3. The method of claim 1, wherein said automatically converting said cleansing rule comprises:

defining a window in SQL/OLAP to include a set of rows of said sequence-based data, said set of rows referred to by a condition of said cleansing rule; and

converting said condition to a case expression in SQL/OLAP over said window, wherein said condition refers to a singleton and said set of rows.

4. The method of claim 1, wherein said automatically converting said cleansing rule comprises one of:

implementing an action of said cleansing rule as a filter condition in SQL/OLAP, if said action is a delete action or a keep action, wherein said delete action removes one or more rows of said sequence-based data and said keep action retains one or more rows of said sequence-based data; and

converting said action of said cleansing rule to a case expression in SQL/OLAP if said action is a modify action, wherein said modify action modifies one or more rows of said sequence-based data.

5. The method of claim 4, wherein said automatically converting said cleansing rule comprises said implementing said action as said filter condition, wherein a rule condition of said cleansing rule is utilized directly as said filter condition if said action is said keep action, and wherein a negation of said rule condition is utilized as said filter condition if said action is said delete action.

6. The method of claim 1, wherein said automatically rewriting further includes:

performing at least one of;

an expanded rewrite algorithm and a join-back algorithm to generate said rewritten query, said performing including;

reducing said sequence-based data to a subset of said sequence-based data, said subset to be used by a generation of cleansed data, and executing, subsequent to said reducing, logic included in said user query on said cleansed data,

wherein said reducing said sequence-based data to said subset and said executing said logic included in said user query provide an assurance that said answer provided by said executing said rewritten query is identical to said result of said executing said user query on said set of data generated by said application of said cleansing rule to all of said sequence-based data.

7. The method of claim 6, wherein said automatically rewriting includes said performing said expanded rewrite algorithm, and wherein said performing said expanded rewrite algorithm further includes:

for each context reference X of one or more context references included in a pattern of said cleansing rule (C) on a relational table R, performing a loop that includes;

setting a correlation condition cr to a list of one or more conjuncts, said one or more conjuncts comprising at least one of;

one or more explicit conjuncts included in a condition of said cleansing rule C and referring to said context reference X and one or more implied conjuncts, each implied conjunct being on a cluster key of said relational table R or a sequence key of said relational table R, wherein said correlation condition cr is a correlation condition between said context reference X and T, said T being a target reference included in said pattern,

if said context reference X is a position-based context reference, then retaining in said one or more conjuncts of said correlation condition cr only position-preserving conjuncts,

binding s to said target reference T, wherein said s is a query condition on said relational table R and is included in said user query (Q),

running a transitivity analysis between said correlation condition cr and said query condition s,

determining d, said d being a set including any conjunct of a condition generated through said transitivity analysis that refers only to said context reference X, and

if set d is not empty, adding set d to a context condition cc, otherwise setting said context condition cc to an empty set and breaking out of said loop, wherein said context condition cc defines a context set for context reference X; and

if said context condition cc is not said empty set, generating an expanded rewrite Q_e as said rewritten query, otherwise setting said expanded rewrite Q_e to a null value.

8. The method of claim 7, wherein said generating said expanded rewrite Q_e comprises:

computing an expanded condition ec as s∥

cc;

simplifying said query condition s to an optimized query condition s′

, said simplifying including setting said optimized query condition s′

equal to s−

cc; and

computing said expanded rewrite Q_e by an expression σ

_s′

(Φ

_c(σ

_ec(R))), wherein said Φ

_c(σ

_ec(R)) is a result of applying said cleansing rule C on a data set σ

_ec(R), wherein said data set σ

_ec(R) is a result of directly pushing said expanded condition ec to said relational table R and cleansing data of said relational table R selected by said expanded condition ec.

9. The method of claim 7, wherein said user query is of a form σ

_sR_K1σ

_S1D₁ . . . _Knσ

_SnD_n,

wherein said relational table R joins each table D_i on column K_i by n;

1 joins,

wherein said any conjunct generated through said transitivity analysis is P_i on tables D′

_i, wherein i=1, . . . , m and m<

=n, and

wherein said performing said expanded rewrite algorithm further includes;

ordering said D′

_i in ascending selectivity order of S′

_i for i=1, . . . , m;

performing a loop utilizing a counter incremented over a series of m+1 values, said performing said loop utilizing said counter including;

if said counter is equal to an initial value, generating a first SQL statement that defers all of said joins after a cleansing of said sequence-based data, said cleansing including utilizing said cleansing rule, otherwise generating an additional SQL statement that joins said relational table R with said tables D′

₁ to D′

_i in an order specified by said ordering,

converting each join condition associated with said n;

1 joins to a local conjunct on said relational table R of the form R.K_i in (select K_i from D_i where S_i),

performing said expanded rewrite algorithm of claim 7,

generating a new SQL statement if all “

in”

conjuncts are derived on said context reference, said generating said new SQL statement including utilizing said performing said expanded rewrite algorithm of claim 7, and

converting said “

in”

conjuncts to joins if all of said “

in”

conjuncts are derived on said context reference;

compiling a set of up to m+1 SQL statements comprising said first SQL statement and said additional SQL statements generated by said loop utilizing said counter, said compiling including utilizing an optimizer of said DBMS;

determining, by said DBMS, estimates of costs of computing resources required for an execution of said SQL statements included in said set of up to m+1 SQL statements; and

selecting, as said rewritten query and subsequent to said determining, an optimal SQL statement from said set of up to m+1 SQL statements, said optimal SQL statement being associated with a least estimate of said determined estimates.

10. The method of claim 6, wherein said automatically rewriting includes said performing said join-back algorithm, and wherein said performing said join-back algorithm further includes:

ordering D₁ to D_n in ascending selectivity order of S_i, wherein said user query (Q) is of a form σ

_sR_JC1σ

_S1D₁ . . . _JCnσ

_SnD_n in which said user query Q is said σ

_sR and a relational table R joins each table D_i using condition JCi;

generating n+1 SQL queries Q_i, said generating said n+1 SQL queries Q_i including pushing from 0 to n semi-joins in an order specified by said ordering;

compiling said n+1 SQL queries Q[i], said compiling including utilizing an optimizer of said DBMS;

determining, by said DBMS, estimates of costs of computing resources required for an execution of each SQL query Q[i]; and

selecting, as said rewritten query and subsequent to said determining, an SQL query Q_j of said n+1 SQL queries Q[i], said SQL query Q_j being associated with a least estimate of said determined estimates.

11. The method of claim 10, wherein said generating said n+1 SQL queries Q[i] comprises:

setting a counter to an initial value; and

for said counter less than or equal to a terminal value, performing a loop that includes;

if said counter is equal to said initial value, setting T to a first projection π

_ckey(σ

_sR), otherwise setting T to a second projection σ

_ckey(σ

_sR_JCiσ

_SiD₁ . . . _JCiσ

_SiD_i), wherein said first projection and said second projection project input data of said first projection and said second projection, respectively, on ckey and remove duplicates therein, said ckey being a cluster key included in a definition of cleansing rule C, and wherein said setting T to said first projection and setting T to said second projection facilitate said pushing;

generating Q[i] as an expression σ

_s′

(Φ

_c(σ

_ec(R)_ckey(T))), wherein ec is an expanded condition and s′

is an optimized query condition, wherein said Φ

_c(σ

_ec(R)_ckey(T)) is a result of applying said cleansing rule C on a data set σ

_ec(R), wherein said data set σ

_ec(R) is a result of directly pushing said expanded condition ec to said relational table R and cleansing data of said relational table R selected by said expanded condition ec, and wherein said generating includes;

computing said expanded condition ec as s∥

cc, wherein said s is a query condition on said relational table R and is included in said user query Q, and wherein said cc is a context condition defining a context set for a context reference X, said context reference X included in one or more context references included in a pattern of said cleansing rule C, and

simplifying said query condition s to said optimized query condition s′

, said simplifying including setting said optimized query condition s′

equal to s−

cc; and

incrementing said counter.

12. The method of claim 6, wherein said automatically rewriting further includes:

performing said expanded rewrite algorithm to rewrite said user query as query Q_e;

performing said join-back algorithm to rewrite said user query as query Q_j; and

determining a first cost estimate associated with one or more computing resources required to execute said query Q_e;

determining a second cost estimate associated with said one or more computing resources required to execute said query Q_j;

selecting said query Q_e as said rewritten query if said first cost estimate is less than said second cost estimate; and

selecting said query Q_j as said rewritten query if said second cost estimate is less than said first cost estimate.

13. A computer program product, comprising a computer-usable medium having a computer-readable program code embodied therein, said computer-readable program code comprising an algorithm adapted to implement the method of claim 1.

14. A system for cleansing anomalies from sequence-based data at query time in a computing environment, comprising:

means for loading sequence-based data into a database managed by a database management system (DBMS) of a computing system, said loading being performed at a load time of said sequence-based data that precedes a query time of said sequence-based data;

means for receiving a cleansing rule at a cleansing rules engine of said computing system;

means for automatically converting, by said cleansing rules engine, said cleansing rule to a template, said template including logic to compensate for one or more anomalies in said sequence-based data;

means for receiving, at said query time and by a query rewrite engine of said computing system, a user query to retrieve said sequence-based data;

means for automatically rewriting, at said query time and by said query rewrite engine, said user query to provide a rewritten query, said means for automatically rewriting including means for applying said logic included in said template to compensate for said one or more anomalies; and

means for executing, at said query time, said rewritten query by said DBMS, wherein an answer provided by said means for executing said rewritten query is identical to a result provided by a means for executing said user query on a set of data generated by an application of said cleansing rule to all of said sequence-based data.

15. The system of claim 14, wherein said means for automatically rewriting further includes:

means for performing at least one of;

an expanded rewrite algorithm and a join-back algorithm to generate said rewritten query, said means for performing including;

means for reducing said sequence-based data to a subset of said sequence-based data, said subset to be used by a generation of cleansed data, and

means for executing, subsequent to said reducing, logic included in said user query on said cleansed data,

wherein said means for reducing said sequence-based data to said subset and said means for executing said logic included in said user query provide an assurance that said answer provided by said executing said rewritten query is identical to said result of said executing said user query on said set of data generated by said application of said cleansing rule to all of said sequence-based data.

16. The system of claim 15, wherein said means for automatically rewriting includes said means for performing said expanded rewrite algorithm, and wherein said means for performing said expanded rewrite algorithm further includes:

means for performing a loop for each context reference X of one or more context references included in a pattern of said cleansing rule (C) on a relational table R, said means for performing said loop including;

means for setting a correlation condition cr to a list of one or more conjuncts, said one or more conjuncts comprising at least one of;

one or more explicit conjuncts included in a condition of said cleansing rule C and referring to said context reference X and one or more implied conjuncts, each implied conjunct being on a cluster key of said relational table R or a sequence key of said relational table R, wherein said correlation condition cr is a correlation condition between said context reference X and T, said T being a target reference included in said pattern,

means for retaining in said one or more conjuncts of said correlation condition cr only position-preserving conjuncts, if said context reference X is a position-based context reference,

means for binding s to said target reference T, wherein said s is a query condition on said relational table R and is included in said user query (Q),

means for running a transitivity analysis between said correlation condition cr and said query condition s,

means for determining d, said d being a set including any conjunct of a condition generated through said transitivity analysis that refers only to said context reference X, and

means for adding set d to a context condition cc if set d is not empty, and otherwise for setting said context condition cc to an empty set and breaking out of said loop, wherein said context condition cc defines a context set for context reference X; and

means for generating, if said context condition cc is not said empty set, an expanded rewrite Q_e as said rewritten query, and otherwise for setting said expanded rewrite Q_e to a null value.

17. The system of claim 16, wherein said means for generating said expanded rewrite Q_e comprises:

means for computing an expanded condition ec as s∥

cc;

means for simplifying said query condition s to an optimized query condition s′

, said

means for simplifying including means for setting said optimized query condition s′

equal to s−

cc; and

means for computing said expanded rewrite Q_e by an expression σ

_s′

(Φ

_c(σ

_ec(R))), wherein said Φ

_c(σ

_ec(R)) is a result of applying said cleansing rule C on a data set σ

_ec(R), wherein said data set σ

_ec(R) is a result of directly pushing said expanded condition ec to said relational table R and cleansing data of said relational table R selected by said expanded condition ec.

18. The system of claim 16, wherein said user query is of a form σ

_sR_K1σ

_S1D₁ . . . _Knσ

_SnD_n,

wherein said relational table R joins each table D_i on column K_i by n;

1 joins,

wherein said any conjunct generated through said transitivity analysis is P_i on tables D′

_i,

wherein i=1, . . . , m and m<

=n, and

wherein said means for performing said expanded rewrite algorithm further includes;

means for ordering said D′

_i in ascending selectivity order of S′

_i for i=1, . . . , m;

means for performing a loop utilizing a counter incremented over a series of m+1 values, said means for performing said loop utilizing said counter including;

if said counter is equal to an initial value, means for generating a first SQL statement that defers all of said joins after a cleansing of said sequence-based data, said cleansing including utilizing said cleansing rule, otherwise means for generating an additional SQL statement that joins said relational table R with said tables D′

₁ to D′

_i in an order specified by said ordering,

means for converting each join condition associated with said n;

1 joins to a local conjunct on said relational table R of the form R.K_i in (select K_i from D_i where S_i),

means for performing steps of said expanded rewrite algorithm of claim 7,

means for generating a new SQL statement if all “

in”

conjuncts are derived on said context reference, said means for generating said new SQL statement including means for utilizing said performing said steps of said expanded rewrite algorithm of claim 7, and

means for converting said “

in”

conjuncts to joins if all of said “

in”

conjuncts are derived on said context reference;

means for compiling a set of up to m+1 SQL statements comprising said first SQL statement and said additional SQL statements generated by said loop utilizing said counter, said means for compiling including means for utilizing an optimizer of said DBMS;

means for determining, by said DBMS, estimates of costs of computing resources required for an execution of said SQL statements included in said set of up to m+1 SQL statements; and

means for selecting, as said rewritten query and subsequent to said determining, an optimal SQL statement from said set of up to m+1 SQL statements, said optimal SQL statement being associated with a least estimate of said determined estimates.

19. The system of claim 15, wherein said means for automatically rewriting includes said means for performing said join-back algorithm, and wherein said means for performing said join-back algorithm further includes:

means for ordering D₁ to D_n in ascending selectivity order of Si, wherein said user query (Q) is of a form σ

_sR_JC1σ

_S1D₁ . . . _JCnσ

_SnD_n in which said user query Q is said σ

_sR, and a relational table R joins each table D1 using condition JCi;

means for generating n+1 SQL queries Q1, said means for generating said n+1 SQL queries Q_i including means for pushing from 0 to n semi-joins in an order specified by said ordering;

means for compiling said n+1 SQL queries Q[i], said means for compiling including means for utilizing an optimizer of said DBMS;

means for determining, by said DBMS, estimates of costs of computing resources required for an execution of each SQL query Q[i]; and

means for selecting, as said rewritten query and subsequent to said determining, an SQL query Q_j of said n+1 SQL queries Q[i], said SQL query Q_j being associated with a least estimate of said determined estimates.

20. The system of claim 19, wherein said means for generating said n+1 SQL queries Q[i] comprises:

means for setting a counter to an initial value; and

means for performing a loop for said counter less than or equal to a terminal value, said means for performing said loop including;

means for setting T to a first projection π

_ckey(σ

_sR) if said counter is equal to said initial value, otherwise for setting T to a second projection π

_ckey(σ

_sR_JCiσ

_SiD₁ . . . _JCiσ

_SiD_i), wherein said first projection and said second projection project input data of said first projection and said second projection, respectively, on ckey and remove duplicates therein, said ckey being a cluster key included in a definition of cleansing rule C, and wherein said setting T to said first projection and setting T to said second projection facilitate said pushing;

means for generating Q[i] as an expression σ

_s′

(Φ

_c(σ

_ec(R)_ckey(T))), wherein ec is an expanded condition and s′

is an optimized query condition, wherein said Φ

_c(σ

_ec(R)_ckey(T)) is a result of applying said cleansing rule C on a data set σ

_ec(R), wherein said data set σ

_ec(R) is a result of directly pushing said expanded condition ec to said relational table R and cleansing data of said relational table R selected by said expanded condition ec, and wherein said means for generating includes;

means for computing said expanded condition ec as s∥

cc, wherein said s is a query condition on said relational table R and is included in said user query Q, and wherein said cc is a context condition defining a context set for a context reference X, said context reference X included in one or more context references included in a pattern of said cleansing rule C, and means for simplifying said query condition s to said optimized query condition s′

, said means for simplifying including means for setting said optimized query condition s′

equal to s−

cc; and

means for incrementing said counter.

21. A computer-implemented method of cleansing anomalies from sequence-based data at query time via a rewrite of a query with respect to multiple cleansing rules, comprising:

loading sequence-based data into a database managed by a database management system (DBMS) of a computing system, said sequence-based data including one or more anomalies;

receiving a plurality of cleansing rules C₁, . . . , C_n at a cleansing rules engine of said computing system;

receiving, by a query rewrite engine of said computing system, a user query Q to retrieve said sequence-based data;

automatically rewriting said user query by said query rewrite engine to provide a rewritten query;

executing said rewritten query by said DBMS, said executing including generating cleansed data from said sequence-based data, said cleansed data not including said one or more anomalies,

wherein said automatically rewriting includes;

for each cleansing rule C_i of said plurality of cleansing rules C₁, . . . , C_n, performing a first loop that includes;

for each context reference X of one or more context references included in a pattern of said cleansing rule C_i on a relational table R, performing a second loop that includes;

setting a correlation condition cr to a list of one or more conjuncts, said one or more conjuncts comprising at least one of;

one or more explicit conjuncts included in a condition of said cleansing rule C_i and referring to said context reference X and one or more implied conjuncts, each implied conjunct being on a cluster key of said relational table R or a sequence key of said relational table R, wherein said correlation condition cr is a correlation condition between said context reference X and T, said T being a target reference included in said pattern,

if said context reference X is a position-based context reference, then retaining in said one or more conjuncts of said correlation condition cr only position-preserving implied conjuncts,

binding s to said target reference X, wherein said s is a query condition on said relational table R and is included in said user query Q,

running a transitivity analysis between said correlation condition cr and said query condition s,

determining d, said d being a set including any conjunct of said correlation condition cr that refers only to context reference X, and

if set d is not empty, adding set d to a context condition cc_i, otherwise setting said context condition cc_i to an empty set and breaking out of said second loop, wherein said context condition cc_i defines a context set for context reference X, and

if said context condition cc_i is said empty set, breaking out of said first loop, and performing a join-back algorithm to generate said rewritten query; and

if no context condition cc_i is said empty set, performing the following;

computing an overall context condition cc as cc₁∥

cc₂ . . . ∥

cc_n,

computing an expanded condition ec as s∥

cc, wherein said s is a query condition of said user query Q,

simplifying said query condition s to an optimized query condition s′

, said simplifying including setting said optimized query condition s′

equal to s−

cc, and

computing an expanded rewrite query Q_e as said rewritten query, said computing said expanded rewrite query Q_e including utilizing an expression σ

_s′

(Φ

_Cn . . . Φ

_C1(σ

_ec(R))), wherein each Φ

_Ci(σ

_ec(R)) of said Φ

_Cn . . . Φ

_C1(σ

_ec(R)) is a result of applying said cleansing rule C_i on a data set σ

_ec(R), wherein said data set σ

_ec(R) is a result of directly pushing said expanded condition ec to said relational table R and cleansing data of said relational table R selected by said expanded condition ec.

22. A system for cleansing anomalies from sequence-based data at query time via a rewrite of a query with respect to multiple cleansing rules in a computing environment, comprising:

means for loading sequence-based data into a database managed by a database management system (DBMS) of a computing system, said sequence-based data including one or more anomalies;

means for receiving a plurality of cleansing rules C₁, . . . , C_n at a cleansing rules engine of said computing system;

means for receiving, by a query rewrite engine of said computing system, a user query Q to retrieve said sequence-based data;

means for automatically rewriting said user query by said query rewrite engine to provide a rewritten query;

means for executing said rewritten query by said DBMS, said means for executing including means for generating cleansed data from said sequence-based data, said cleansed data not including said one or more anomalies,

wherein said means for automatically rewriting includes;

means for performing a first loop for each cleansing rule C_i of said plurality of cleansing rules C₁, . . . , C_n, said means for performing said first loop including;

means for performing a second loop for each context reference X of one or more context references included in a pattern of said cleansing rule C_i on a relational table R, said means for performing said second loop including the following;

means for setting a correlation condition cr to a list of one or more conjuncts, said one or more conjuncts comprising at least one of;

one or more explicit conjuncts included in a condition of said cleansing rule C_i and referring to said context reference X and one or more implied conjuncts, each implied conjunct being on a cluster key of said relational table R or a sequence key of said relational table R, wherein said correlation condition cr is a correlation condition between said context reference X and T, said T being a target reference included in said pattern,

means for retaining in said one or more conjuncts of said correlation condition cr only position-preserving implied conjuncts if said context reference X is a position-based context reference,

means for binding s to said target reference X, wherein said s is a query condition on said relational table R and is included in said user query Q,

means for running a transitivity analysis between said correlation condition cr and said query condition s,

means for determining d, said d being a set including any conjunct of said correlation condition cr that refers only to context reference X, means for adding set d to a context condition cc_i if set d is not empty, and otherwise for setting said context condition cc_i to an empty set and breaking out of said second loop, wherein said context condition cc_i defines a context set for context reference X, and

means for breaking out of said first loop if said context condition cc_i is said empty set, and means for performing a join-back algorithm to generate said rewritten query; and

means for performing the following if no context condition cc_i is said empty set;

computing an overall context condition cc as cc₁∥

cc₂ . . . ∥

cc_n,

computing an expanded condition ec as s∥

cc, wherein said s is a query condition of said user query Q,

simplifying said query condition s to an optimized query condition s′

, said simplifying including setting said optimized query condition s′

equal to s−

cc, and

computing an expanded rewrite query Q_e as said rewritten query, said computing said expanded rewrite query Q_e including utilizing an expression σ

_s′

(Φ

_Cn . . . Φ

_C1(R))), wherein each Φ

_Ci(σ

_ec(R)) of said Φ

_Cn . . . Φ

_C1(ν

_ec(R)) is a result of applying said cleansing rule C_i on a data set σ

_ec(R), wherein said data set σ

_ec(R) is a result of directly pushing said expanded condition ec to said relational table R and cleansing data of said relational table R selected by said expanded condition cc.