TRANSLATION OF STREAMING QUERIES INTO SQL QUERIES

• US 20090319501A1
• Filed: 06/24/2008
• Published: 12/24/2009
• Est. Priority Date: 06/24/2008
• Status: Abandoned Application

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Hong, Mingsheng, Goldstein, Jonathan David
• Application Number:
  US12/144,698
• Publication Number:
  US 20090319501A1
• Time in Patent Office: Days
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2452 Query translation
• CPC Class Codes: G06F 16/24568 Data stream processing; Continuous queries
• CPC Class Codes: G06F 16/258 Data format conversion from or to a database

Abstract

A query translation system and method for processing a streaming language query on existing or stored data. The streaming language query is applied against a data stream log by first translating the streaming language query into a database management system query (such as a SQL query) and then applying the translated streaming language query against the data stream log. Embodiments of the query translation system and method include a bitemporal converter that converts a bitemporal data stream log into a canonical history table format. Once in this format, embodiments of the query translation system and method translate a streaming language query into a SQL query. A categorization of each of the streaming operators that make up the streaming language query is performed to determine which translation technique to use. In general, one of three general translation techniques is used based on these categorizations of the streaming operators.

Claims

1. A computer-implemented method for processing a streaming language query of a data stream log stored in a file system, comprising:

translating the streaming language query into a database management system query; and

evaluating the database management system query against the data stream log to obtain query results.

2. The computer-implemented method of claim 1, further comprising:

archiving the data stream to obtain an archived data stream log; and

determining whether the archived data stream log is in a canonical history table format;

if the archived data stream log is in a canonical history table format, then outputting a cleaned-up data stream log in canonical history table format; and

if the archived data stream log is not in a canonical history table format, then determining that the archived data stream log is a log of an archived bitemporal data stream log;

wherein the data stream log is the cleaned-up data stream log.

3. The computer-implemented method of claim 2, further comprising:

determining retraction events in the archived bitemporal data stream log;

incorporating the retraction events into content changes of a virtual relation;

generating a canonical history table of the archived bitemporal data stream log using the content changes of the virtual relation to store the eventual content of the virtual relation such that tuple ordering is immaterial to generate the cleaned-up data stream log in canonical history table format; and

outputting the cleaned-up data stream log in canonical history table format.

4. The computer-implemented method of claim 1, further comprising:

defining the streaming language query as a composition of streaming operators;

categorizing each of the streaming operators in the composition as one of;

(1) SQL-like operator;

(b) snapshot-oriented operator;

(c) group&

Apply operator;

translating each of the streaming operators in the composition separately using a translation technique that is selected based on the categorization to obtain translation results for each of the streaming operators; and

composing the translation results for each of the streaming operators to generate the database management system query.

5. The computer-implemented method of claim 4, further comprising:

categorizing the streaming operator as a SQL-like operator; and

determining a type of SQL-like operator of the streaming operator.

6. The computer-implemented method of claim 5, further comprising:

determining that the streaming operator is a stateless operator and determining a type of stateless operator;

if the stateless operator is a SELECTION operator, then using a SELECTION translation technique to obtain the database management system query;

if the stateless operator is a PROJECT operator, then using a PROJECT operator translation technique to obtain the database management system query;

if the stateless operator is an ALTERLIFETIME operator, then using an ALTERLIFETIME operator translation technique to obtain the database management system query; and

if the stateless operator is a UNION operator, then using a UNION operator translation technique to obtain the database management system query.

7. The computer-implemented method of claim 5, further comprising:

determining that the streaming operator is a JOIN operator; and

using a JOIN translation technique to obtain the database management system query.

8. The computer-implemented method of claim 4, further comprising:

categorizing the streaming operator as a snapshot-oriented operator;

defining C as an array of end points of valid intervals of tuples in the data stream; and

generating the C array using a CREATEVIEW statement in a structured query language.

9. The computer-implemented method of claim 8, further comprising:

defining a relation, D, as a relation containing piecewise segments of points in the C array;

generating the relation, D, using a CREATEVIEW statement in a structured query language;

determining whether multi-dimensional indexing is available;

if multi-dimensional indexing is available, then iterating over D to correlate D and the data stream;

if multi-dimensional indexing is not available, then iterating over the data stream to correlate D and the data stream; and

use the correlation between D and the data stream to obtain a translated snapshot-oriented operator as a database management system query.

10. The computer-implemented method of claim 8, further comprising:

defining a relation, D, in terms of a RANK function in a structured query language;

generating the relation, D, using a CREATEVIEW statement in a structured query language;

determining whether multi-dimensional indexing is available;

if multi-dimensional indexing is available, then iterating over D to correlate D and the data stream;

if multi-dimensional indexing is not available, then iterating over the data stream to correlate D and the data stream; and

use the correlation between D and the data stream to obtain a translated snapshot-oriented operator as a database management system query.

11. The computer-implemented method of claim 4, further comprising:

categorizing the streaming language query as a GROUP&

APPLY operator;

defining a GROUPBY attribute X;

defining an APPLY expression, which is a complex event detection and response (CEDR) expression, to apply to each substream of the data stream, S, defined by tuples in S with the same X value;

translating the GROUP&

APPLY operator in the APPLY expression to a table-valued function using a value of the GROUPBY attribute X as an input parameter;

using a SELECT DISTINCT statement to obtain a set V, where V is a set of distinctly X values in S;

for each value v in V, evaluating the table-valued function corresponding to a top-level operator of the APPLY expression by using a CROSS APPLY operator to generate a translated GROUP&

APPLY operator as a database management system query.

12. A method for translating a streaming language query into a structured query language (SQL) query, comprising:

input the streaming language query;

defining the streaming language query as a composition of streaming operators;

categorizing each of the streaming operators in the composition;

translating each of the streaming operators in the composition separately using a translation technique selected based on the categorization;

if the streaming operator is categorized as a SQL-like operator, then translating the streaming operator using a SQL-like operator translation technique;

if the streaming operator is categorized as a snapshot-oriented operator, then translating the streaming operator using a snapshot-oriented operator translation technique;

if the streaming operator is categorized as a GROUP&

APPLY operator, then translating the streaming operator using a GROUP&

APPLY operator translation technique;

composing translation results of the translation of each of the streaming operators to generate a SQL query; and

output the SQL query that is a translation of the streaming language query.

13. The method of claim 12, further comprising:

defining the streaming language query as a complex event detection and response (CEDR) query, Q;

defining Q as Q=ν

(Q₁)⁵, where, ν

is a unary CEDR operator, and Q₁ is a first CEDR query; and

defining a translation function, T[.], as T[Q]=(T[ν

])(T[Q₁]). and

using the translation function to translate the streaming language query into a SQL query.

14. The method of claim 12, further comprising:

defining the streaming language query as a complex event detection and response (CEDR) query, Q;

defining Q as Q=ν

(Q₁, Q₂), where, ν

is a binary CEDR operator, and Q₁ is a first CEDR query and Q₂ is a second CEDR query;

defining a translation function, T[.], as T[Q]=(T[ν

])(T[Q_1],T[Q2]). and

using the translation function to translate the streaming language query into a SQL query.

15. The method of claim 12, further comprising:

defining one of the streaming operators as a snapshot-oriented operator;

defining a C array as an array of end points of valid intervals of tuples in a data stream, S, the valid interval having a valid start time, V_s, and a valid end time, V_e;

generating the C array using the following SQL statement;

CREATE VIEW V_C AS SELECT DISTINCT V_S AS Point FROM S UNION SELECT DISTINCT V_e AS Point FROM S;

defining a relation, D, as a relation containing piecewise segments of points in the C array;

generating the relation, D, using the following SQL statement;

CREATE VIEW RankedC AS SELECT Point, rank( ) OVER (ORDER BY Point) AS Rank FROM V_C CREATE VIEW D AS SELECT C1.Point AS start, C2.Point AS end FROM RankedC AS C1, RankedC AS C2 WHERE C2.Rank = C1.Rank+1;

correlating D and S to obtain a translated snapshot-oriented operator as a portion of a SQL query.

16. The method of claim 15, further comprising:

determining that multi-dimensional indexing is available; and

iterating over D for a given tuple in D using a CROSS APPLY operator to aggregate over relevant tuples in S using the following SQL statement;

CREATE VIEW AggResult AS SELECT D.V_S AS V_S, D.V_e AS V_e, AggValue FROM D CROSS APPLY (  

SELECT AGGTYPE(X) AS AggValue  

FROM S  

WHERE S. V_S <

= D.V_S AND S.V_e >

= D.V_e ) AS ApplyResult.

17. The method of claim 15, further comprising:

determining that multi-dimensional indexing is not available; and

iterating over S by joining D with S to obtain shredded tuples using the following SQL statement;

CREATE VIEW ShreddedInput AS SELECT D.V_S AS V_S, D.V_e AS V_e, P FROM S, D WHERE S.V_S <

= D.V_S AND S.V_e >

D.V_S; and

aggregating the shredded tuples according to their valid interval values using the following SQL statement;

CREATE VIEW AggResult AS SELECT V_S, V_e, AGGTYPE(X) FROM ShreddedInput GROUP BY V_S, V_e.

18. A process for applying a structured query language (SQL) query to a data stream log, comprising:

generating a streaming language query for the data stream log;

defining the streaming language query as a composition of streaming operators;

categorizing each of the streaming operators as one of;

(a) a SQL-like operator;

(b) a snapshot-oriented operator;

(c) a GROUP&

APPLY operator;

translating each of the streaming operators in the composition separately into a corresponding SQL operator using a translation technique selected based on the categorization of the streaming operator;

composing translation results obtained from the translation of each of the streaming operators to generate the SQL query; and

applying the translated streaming language query as the SQL query to the data stream log to obtain a query results log.

19. The process as set forth in claim 18, further comprising:

categorizing one of the streaming operators as a complex event detection and response (CEDR) join operator; and

translating the CEDR join operator into a corresponding SQL operator using the following SQL statement;

SELECT max(S1. V_s, S2. V_s) AS V_s, min(S1. V_e, S2.V_e) AS V_e, P FROM S1, S2, WHERE θ

^SQL AND S1.V_s<

S2.V_e AND S2.V_s<

S1V_e;

wherein P is payload attributes of input streams S₁ and S_{2, and θ}

^SQL is a join predicate θ

in SQL syntax.

20. The process as set forth in claim 18, further comprising:

categorizing one of the streaming operators as a AlterLifeTime operator; and

translating the AlterLifeTime operator into a corresponding SQL operator using the following SQL statement;

CREATE VIEW V_{0 AS SELECT Vs}, V_s+2 AS V_e, tid FROM S;

wherein S is an input stream, tid is a thread identification, V is a valid interval of tuples in the input stream, S, wherein the valid interval has a valid start time, V_s, and a valid end time, V_e.