Ex Parte Lawande et al

Patent Trial and Appeal Board

May 7, 2013

10936469 (P.T.A.B. May. 7, 2013)

UNITED STATES PATENT AND TRADEMARK OFFICE
____________

BEFORE THE PATENT TRIAL AND APPEAL BOARD
____________

Ex parte SHILPA LAWANDE, MOHAMED ZIAUDDIN,
and GREGORY SCOTT SMITH
____________

Appeal 2010-011195
Application 10/936,469
Technology Center 2100
____________

Before BRUCE R. WINSOR, BARBARA A. BENOIT, and
DANIEL N. FISHMAN, Administrative Patent Judges.

FISHMAN, Administrative Patent Judge.

DECISION ON APPEAL
Appellants appeal under 35 U.S.C. § 134(a) from the Examiner’s final
rejection of claims 1-27. App. Br. 2.1 We have jurisdiction under 35 U.S.C.
§ 6(b). We affirm.

1 Throughout this opinion, we refer to: (1) the Appeal Brief (“App. Br.”)
filed January 19, 2010 and amended March 2, 2010; (2) the Examiner’s
Answer (“Ans.”) mailed June 3, 2010; and (3) the Reply Brief (“Reply Br.”)
filed August 3, 2010.
Appeal 2010-011195
Application 10/936,469

2
STATEMENT OF THE CASE
The Invention
Appellants’ invention relates to database query optimization. See
generally Abstract. Claim 1 is reproduced below and is illustrative of the
claims at issue on this appeal with disputed limitations emphasized:
1. A method comprising:
identifying a set of high load database query language
statements from a workload by performing a comparison
between performance information for query language
statements in the workload, wherein the workload is a set of
query language statements;
for each statement in the set,
performing an optimization process on the statement;
determining that an access structure for an advanced
transformation is beneficial for the statement during the
optimization process;
during the optimization process, generating a set of
candidate indexes which could be used to improve an execution
plan for the statement, wherein the set of candidate indexes
comprises index candidates for the access structure;
selecting a subset from the set of candidate indexes using
a model to remove expensive indexes;
identifying an index in the subset that can satisfy a
different statement;
consolidating the identified index in the subset with an
index for the different statement;
determining an execution plan using a processor for the
statement using the subset of indexes; and
storing the execution plan in a medium.
The Examiner relies on the following as evidence of unpatentability:
Agrawal US 6,366,903 B1 Apr. 2, 2002
Brown US 2003/0093408 A1 May 15, 2003
Kosciusko US 2007/0038618 A1 Feb. 15, 2007
Earliest Priority Date
May 25, 2001
Appeal 2010-011195
Application 10/936,469

3
The Rejections
Claims 1-4, 6-12, 14-20, and 22-27 stand rejected under 35 U.S.C. §
103(a) as unpatentable over Brown and Agrawal. Ans. 3-12.
Claims 5, 13, and 21 stand rejected under 35 U.S.C. § 103(a) as
unpatentable over Brown, Agrawal, and Kosciusko. Ans. 12-13.2

CLAIMS 1-4, 6-12, 14-20, AND 22-27
The Examiner rejects claim 1 finding that Brown teaches the steps of
the claim but does not explicitly disclose determining that an access
structure for an advanced transformation is beneficial for the statement
during the optimization process and does not show wherein the set of
candidate indexes comprises index candidates for the access structure. Ans.
3-5. The Examiner then finds that Agrawal discloses these features citing
column 7, lines 48-63, and Figure 2 and reasons that the combination of
Brown and Agrawal would be obvious “to improve query performance by
providing characteristics that a traditional index does not have.” Ans. 5-6.
Appellants’ arguments (App. Br. 8-11; Reply Br. 2-6) raise three issues as
discussed below.
Issue #1
Does Brown disclose using a model to remove expensive indexes?

2 The Examiner withdrew the rejection of claims 1-8 and 25 under § 101.
Ans. 2. The Examiner does not clearly indicate withdrawal of the rejection
of claims 9-24, 26, and 27 under § 101 but rather indicates interpretation of
the claims to fall within a statutory class. Id. We review the claims on appeal
presuming that the § 101 rejection has been withdrawn with respect to all
claims.
Appeal 2010-011195
Application 10/936,469

4
Analysis
The Examiner finds that Brown teaches using a model to remove
expensive indexes, citing paragraph 0148 for disclosing “[t]he query index
candidates are searched and analyzed to obtain an optimal set of index
configurations for the query.” Ans. 4. Appellants argue that Brown fails to
show using a model to remove expensive indexes. App. Br. 8-9; Reply Br. 2-
3. More specifically, Appellants argue that an “optimal” set of index
configurations does not teach removing expensive indexes because
“optimization may be performed with respect to different parameters, not
necessarily with respect to expensive indexes.” App. Br. 8-9. Appellants
further argue that Brown’s optimal set of index configurations also fails to
use a model for its selection. Id. We are unpersuaded.
The Examiner explains that Brown paragraph 0045 discloses that the
optimizer module identifies a query plan that has a low response time. Ans.
14. The Examiner also explains that Brown paragraph 0045 discloses that a
“cost model” is used to estimate the response time of a query plan. Id. As
also explained by the Examiner, Brown paragraph 0045 teaches that using
the cost model (based on response time) in selecting an optimal set of index
configurations “effectively removes non-optimal indexes.” Id. We agree.
“Expense” and “cost” are synonyms. The expense of a query can be
measured as a cost with respect to a number of parameters—response time
would have been an obvious parameter to be optimized, as is explicitly
taught by Brown. See Brown ¶ 0045; see also ¶ 0145. We find that non-
optimal indexes that increase cost/expense as measured by response time
would be unselected or removed from the optimal set of index
configurations in Brown. Further, we find that removing expensive indexes
Appeal 2010-011195
Application 10/936,469

5
based on cost as measured by response time in Brown teaches use of a
model as recited. We therefore find that Brown teaches using a model to
remove expensive indexes.
Issue #2
Does the combination of Brown and Agrawal teach determining that
an access structure for an advanced transformation is beneficial for the
statement during the optimization process?
Analysis
The Examiner finds that Agrawal teaches determining that an access
structure for an advanced transformation is beneficial for the statement
during the optimization process citing column 7, lines 48-63. Ans. 5.
Agrawal discloses a candidate selection module 225 that works with
optimizer 240 to “identif[y] which indexes and materialized views would be
likely to be used on a given query.” Agrawal col. 7, ll. 53-54. The Examiner
maps these identified indexes and materialized views to the recited access
structure. Ans. 6. Agrawal also discloses:
The likely to be used materialized views are selectively merged
to form a set of merged materialized views. The merged
materialized views are combined with the likely to be used
materialized views to form a candidate set of materialized
views. The candidate set will be further explored at an
enumeration module 250. A search is performed among these
structures to determine the ideal physical design, henceforth
called a configuration, which consists of a set of traditional
indexes, materialized views and indexes on materialized views.
Agrawal col. 7, ll. 54-63. The Examiner maps this “configuration” of
Agrawal to the recited advanced transformation. Ans. 6.
Appellants argue that the Examiner improperly reads the recited
“access structure” and “advanced transformation” on the same feature of
Appeal 2010-011195
Application 10/936,469

6
Agrawal (i.e., indexes and materialized views). App. Br. 9-10; Reply Br. 3-
4. Appellants further argue that Agrawal does not disclose determining that
the elements so mapped are “beneficial for the statement during the
optimization process.” App. Br. 10; Reply Br. 4. We are not persuaded.
The Examiner explains that the “configuration” of Agrawal consists
of a set of traditional indexes, materialized indexes, and indexes on
materialized views and thus is distinct from an index and a materialized
view. Ans. 15. We note that Agrawal discloses that materialized views likely
to be used for a query (statement) are selectively merged to form a set of
merged materialized views which are, in turn, combined with the likely to be
used materialized views to form a candidate set that are further explored to
eventually generate the “configuration.” Agrawal col. 7, ll. 54-58. We also
note that the Specification exemplifies an “advanced transformation[]” as
“view merging.” Spec. ¶ 00013. Thus, we conclude that “a set of merged
materialized views” as taught by Agrawal is consistent with an exemplary
“advanced transformation” of Appellants’ Specification, which further
bolsters the Examiner’s position that Agrawal’s “configuration” equates
with the recited “advanced transformation.”
Regarding determining that the access structure is “beneficial to the
statement,” the Examiner further explains that the Abstract of Agrawal
discloses that a recommendation of indexes and materialized views are
beneficial given a specified workload, and that a workload is a “statement.”
Ans. 16 (citing Agrawal Abstract (“An index and materialized view
selection wizard produces a fast and reasonable recommendation of indexes
and materialized views which are beneficial given a specified workload for a
given database and database server.”); Agrawal col. 2, ll. 38-39 (“A
Appeal 2010-011195
Application 10/936,469

7
workload is a set of queries.”)). Regarding the limitation that the
determination is “during the optimization process,” the Examiner explains
that Agrawal’s selection of materialized views and indexes (i.e., access
structure) to create a configuration (i.e., advanced transformation) of
Agrawal is performed during an optimization process. Ans. 16 (citing
Agrawal’s Fig. 2 describing an optimization process).
We agree and therefore find that Agrawal shows the step determining
that an access structure for an advanced transformation is beneficial for the
statement during the optimization process.
Issue #3
Does Brown disclose identifying an index in the subset that can
satisfy a different statement and consolidating the identified index in the
subset with an index for the different statement?
Analysis
The Examiner finds that Brown paragraph 0158 shows the identifying
and consolidating steps. Ans. 4-5 (citing portions of “Rule 2” and “Rule 3”
of Brown ¶ 0158). Appellants argue that the Examiner’s mapping of the
identifying step to Rule 2 and the consolidating step to Rule 3 fails to teach
the recited steps because the two rules are mutually exclusive—cannot both
be applied to the same identified index. App. Br. 10-11; Reply Br. 4-6. We
are not persuaded.
We note that each of Rules 1-4 expressed in Brown paragraph 0158
perform the steps of identifying an index (“current list” as expressed in
Brown ¶ 0158) that may satisfy another statement and consolidating the
identified index with another index. For example, Rule 3 of Brown states:
“If a column in the list is a superset of any of the groups in the index group
Appeal 2010-011195
Application 10/936,469

8
list, the current list is inserted into the index group list and the elements of
groups that are the subset of the current list are removed (Rule 3).” Brown ¶
0158. In other words, if the current list (index) is a superset of another list,
the current list is consolidated with the other list and the other list is
removed because the current list satisfies the other statement. Rule 3 alone
expresses both the identifying and consolidating steps. Rule 1 expresses a
similar identification and consolidation of an index (current list) that is a
subset of another list (another statement) such that the current list can be
removed (consolidated because it is satisfied by another statement. Thus, we
find that Brown paragraph 0158 shows the steps of identifying an index in
the subset that can satisfy a different statement and consolidating the
identified index in the subset with an index for the different statement.
In view of the above discussion, we are unpersuaded of error in the
Examiner’s rejection of independent claim 1. Independent claims 9, 17, and
25-27 recite limitations similar to claim 1, are rejected for similar reasons,
and are not argued separately with particularity.3 App. Br. 11; Reply Br. 6.
Since Appellants argue these claims only with reference to the amended
form that was not entered, the arguments are not commensurate with the
claims on appeal. Dependent claims 2-4, 6-8, 10-12, 14-16, 18-20, and 22-24
depend from claims 1, 9, and 17, respectively, and are not argued separately

3 Appellants filed an Amendment after Final Rejection on July 29, 2009, that
was not entered by the Examiner. The filing amended claims 25-27 to
remove a limitation. Appellants assert that the Amendment after Final
Rejection should have been entered and argues the claims in this appeal only
with reference to the claims as amended. Refusal to enter an Amendment
after Final Rejection is a matter to be addressed, if at all, by a timely filed
petition under 37 C.F.R. § 1.181.
Appeal 2010-011195
Application 10/936,469

9
with particularity. App. Br. 11; Reply Br. 6. We therefore sustain the
rejection of claim 1-4, 6-12, 14-20, and 22-27 under § 103.

CLAIMS 5, 13, AND 21
The Examiner rejects claims 5, 13, and 21 as unpatentable over
Brown, Agrawal, and Kosciusko. Ans. 12-13. Appellants present no
arguments regarding this rejection and therefore we summarily sustain the
rejection of claims 5, 13, and 21.

DECISION
The Examiner’s decision rejecting claims 1-4, 6-12, 14-20, and 22-27
is affirmed.
The Examiner’s decision rejecting claims 5, 13, and 21 is summarily
affirmed.
No time period for taking any subsequent action in connection with
this appeal may be extended under 37 C.F.R. § 1.136(a)(1)(iv).

AFFIRMED

babc