Method for cleansing sequence-based data at query time

• US 7,516,128 B2
• Filed: 11/14/2006
• Issued: 04/07/2009
• Est. Priority Date: 11/14/2006
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Rao, Jun, Doraiswamy, Sangeeta T., Colby, Latha Sankar, Thakkar, Hetal
• Primary Examiner(s): Vo; Tim T
• Assistant Examiner(s): Gortayo; Dangelino N
• Application Number:
  US11/559,452
• Publication Number:
  US 20080114744A1
• Time in Patent Office: 875 Days
• Field of Search: 707/1, 707/2, 707/3, 707/4, 707/5, 707/100, 707/104.1
• US Class Current: 1/1
• 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 for cleansing anomalies from sequence-based data at query time. Sequence-based data such as RFID data is loaded into a database. A cleansing rule is received at a cleansing rules engine. The cleansing rule engine converts the cleansing rule 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 and an expanded rewrite technique. 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 C at a cleansing rules engine of said computing system;

automatically converting, by said cleansing rules engine, said cleansing rule C 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 C to all of said sequence-based data, wherein said automatically rewriting 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, wherein said generating said expanded rewrite Q_e includes;

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, and

wherein a result of said automatically rewriting is 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 C to all of said sequence-based data.