Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1998-10-20
2001-06-26
Alam, Hosain T. (Department: 2172)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000, C706S045000, C706S050000, C709S219000, C709S241000, C710S104000, C711S110000, C345S215000, C345S215000
Reexamination Certificate
active
06253195
ABSTRACT:
BACKGROUND OF THE INVENTION
1. The Field of the Invention
The present invention relates to filteringy events, data, or other instances of classes organized in an object-oriented schema. In particular, the present invention relates to constructing and using filtering trees that can be traversed to determine whether an event, data, or another instance satisfies the terms of a query.
2. The Prior State of the Art
Query language has been used for years to define the parameters used to select and retrieve data stored in relational databases. There are many methods and associated algorithms that have been developed to convert a query-based retrieval definition to computer-executable instructions that identify particular data entries in a relational database that satisfy the query-based retrieval definition. Abstract syntax trees are tools that have been developed for graphically representing the logical operations and order of operations that are executed when processing a query-based definition. Abstract syntax trees are one type of filtering tree, and represent procedures by which data or other types of information can be filtered according to logical operations specified, for example, by query-based definitions.
FIGS. 1A-1C
illustrate abstract syntax trees associated with conventional methods for processing query-based definitions. While conventional methods for processing query-based definitions have proven adequate in some situations, they often become inefficient when applied to large numbers of separate definitions, as will be more fully described below.
The abstract syntax trees of
FIGS. 1A-1C
represent operations executed when processing, respectively, the logical expressions of the following three query-based definitions:
Q1
)
select
*
from
⟨
object
⟩
where
x
>
2
and
y
<
3
Q2
)
select
*
from
⟨
object
⟩
where
x
>
3
Q3
)
select
*
from
⟨
object
⟩
where
not
(
y
≥
5
and
z
>
4
)
In the foregoing query-based definitions, the notation <object> represents any selected object-oriented data class. Turning to
FIG. 1A
, processing the logical expression of query Q
1
is conducted by comparing a data entry in the relational database against the information represented by the nodes of abstract syntax tree
10
. Suppose that a first data entry contained in the relational database has x, y and z parameters with the following values:
D1
)
x
=
4
;
y
=
5
;
and
z
=
2
First, the “and” clause represented by node
11
indicates that both branches that depend therefrom must generate true values for the associated query-based definition to be satisfied. The process of comparing data entry D
1
against query Q
1
proceeds to node
12
which indicates that the operation to be conducted will involve a “greater than” comparison. Next, nodes
13
and
14
specify that the value of the x parameter is to be compared to the number
2
. Because the x parameter of data entry D
1
has a value of 4, the first branch consisting of nodes
12
-
14
generates a true value.
Next, the process steps back to node
12
and proceeds to the second branch, which consists of nodes
15
-
17
. Node
15
indicates that a “less than” operation will be conducted on the second branch. According to nodes
16
and
17
, the y parameter of the data entry is to be compared to the number 3. Since the y parameter has a value of 5, the second branch yields a false value. The process steps back to node
10
and, since the second branch has a false value, data entry D
1
does not satisfy query Q
1
.
In view of the foregoing example, it can be seen that the process represented by abstract syntax tree
10
adequately compares a data entry against the associated query in many situations. However, because of the construction of the abstract syntax tree, both branches were traversed before concluding that the data entry did not satisfy the query. It would have been sufficient to discover that the y parameter of data entry D
1
did not satisfy the logic of query Q
1
without having to consider the x parameter. Thus, the value of the x parameter was unnecessarily compared with query Q
1
in the foregoing example.
Referring now abstract syntax tree
18
of
FIG. 1B
, comparison of data entry D
1
against query Q
2
involves a “greater than” operation according to node
19
. As indicated by nodes
20
and
21
, the process further involves comparing the x parameter of data entry D
1
with the number
3
. Thus, data entry D
1
satisfies query Q
2
.
Comparison of data entry D
1
with query Q
3
is conducted, as shown by abstract syntax tree
22
of
FIG. 1C
, by executing a “not” operation depicted at node
23
. The “not” operation yields a true value if the branch depending therefrom, which includes nodes
24
-
30
in this example, is false. The process advances to node
24
, which indicates that the branch represents an “and” operation. Nodes
25
,
26
, and
27
represent an operation by which it is determined whether the y parameter of data entry D
1
is greater than or equal to 5. In this example, the y parameter of data entry D
1
has a value of
5
, such that the branch of nodes
25
-
27
has a true value. The process steps back to node
24
and then advances to the branch including nodes
28
,
29
, and
30
, which specify that the z parameter of data entry D
1
is compared to the number 4 in a “greater than” operation. Because the z parameter has a value of 2, this branch is false. The process agrain steps back to node
24
, which yields a false value. Stepping back to node
23
, the “not” operation yields a true value, since the “and” operation of node
24
is false.
Abstract syntax trees
18
and
22
adequately compare data entries with the associated queries in many circumstances. However, the configuration of abstract syntax tree
22
required both the y and z parameters to be consecutively considered, whereas the value of the z parameter was sufficient to yield a true value for the abstract syntax tree. A significant disadvantage of the conventional processes for comparing data entries against arises when multiple queries are employed, such as those represented by
FIGS. 1A-1C
. For instance, queries Q
1
and Q
2
both relate to the value of an x parameter. When a data entry is processed using abstract syntax trees
10
and
18
of
FIGS. 1A and 1B
, the x parameter is considered twice. Likewise, the y parameter is separately considered in abstract syntax trees
10
and
22
of
FIGS. 1A and 1C
, respectively. Executing operations multiple times for the same parameter consumes significant computing resources, particularly when the number of separate query-based definitions is large One can imagine applications in which hundreds of queries or more are processed, resulting in repetitive or nearly repetitive operations on the same parameters.
In view of the foregoing, what is needed are methods for constructing and using filtering trees that combine the logical operations of multiple query-based definitions. Such filtering trees would be particularly advantageous if they could be capable of reducing, or eliminating the repetitive execution of operations on the same parameters that has been practiced using conventional techniques.
SUMMARY AND OBJECTS OF THE INVENTION
The present invention relates to systems and method for constructing and using filtering trees that combine logical operations of multiple query-based definitions. The filtering trees of the invention permit an event detected in a computer system, data, or other instances of objects defined in an object-oriented schema to be compared simultaneously with the multiple query-based definitions. The filt
Hudis Irena
McCollum Raymond
Novik Lev
Alam Hosain T.
Alam Shahid
Microsoft Corporation
Workman & Nydegger & Seeley
LandOfFree
Optimized query tree does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Optimized query tree, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Optimized query tree will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2455881