Patent Document ID: 20120246146
Application ID: 13422252
Patent Status: 0

Claim One:
1. A method for processing a multi-way join query, comprising: (a) with respect to a join graph where the respective source streams are denoted by a node and a join predicate is denoted by an edge for the multi-way join query, generating a query walk that is a sequence of nodes and edges in the join graph such that every edge in the join graph is visited at least once in a continuous walk of the join graph starting from a specific node; (b) based on the query walk, generating matrix based synopses for the nodes, where the matrix based synopses include a window synopsis that manages the number of tuples allocated to entries, a window index synopsis that manages a list of addresses of the tuples assigned to the entry, a batch synopsis that is a batch of the window synopsis, and a batch index synopsis that is a batch of the window index synopsis; (c) when a hash function is given to a join attribute domain of the query walk, if the source stream is input, hashing the tuple of the source stream by the hash function to fill the window synopsis, the window index synopsis, the batch synopsis, and the batch index synopsis; (d) when the query equation is defined by the matrix multiplication operation of the window synopses corresponding to the nodes of the query walk, and the batched query equation is defined by the query equation in which a window synopsis corresponding to a specific stream is replaced with a batch synopsis corresponding to the specific stream in the query equation, evaluating the batched query equation to generate a result vector; and (e) based on the result vector, generating the result tuple for the multi-way join query from the batch index synopsis and the window index synopsis.