Ex Parte Day et al

Board of Patent Appeals and Interferences

Aug 5, 2010

10860403 (B.P.A.I. Aug. 5, 2010)

UNITED STATES PATENT AND TRADEMARK OFFICE
UNITED STATES DEPARTMENT OF COMMERCE
United States Patent and Trademark Office
Address: COMMISSIONER FOR PATENTS
P.O. Box 1450
Alexandria, Virginia 22313-1450
www.uspto.gov
APPLICATION NO. FILING DATE FIRST NAMED INVENTOR ATTORNEY DOCKET NO. CONFIRMATION NO.
10/860,403 06/03/2004 Paul Reuben Day ROC920040074US1 9585
46296 7590 08/05/2010
MARTIN & ASSOCIATES, LLC
P.O. BOX 548
CARTHAGE, MO 64836-0548
EXAMINER
GOFMAN, ALEX N
ART UNIT PAPER NUMBER
2162
MAIL DATE DELIVERY MODE
08/05/2010 PAPER
Please find below and/or attached an Office communication concerning this application or proceeding.
The time period for reply, if any, is set in the attached communication.
PTOL-90A (Rev. 04/07)
UNITED STATES PATENT AND TRADEMARK OFFICE
____________

BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________

Ex parte PAUL REUBEN DAY and BRIAN ROBERT MURAS
____________

Appeal 2009-002478
Application 10/860,403
Technology Center 2100
____________

Before JOHN A. JEFFERY, LANCE LEONARD BARRY, and ST. JOHN
COURTENAY, III, Administrative Patent Judges.

BARRY, Administrative Patent Judge.

DECISION ON APPEAL

STATEMENT OF THE CASE
The Patent Examiner rejected claims 1, 2, 4-7, 9-12, 14-20, 22, 23,
27-30, 34, and 35. The Appellants appeal therefrom under 35 U.S.C.
§ 134(a). We have jurisdiction under 35 U.S.C. § 6(b).

Appeal 2009-002478
Application 10/860,403

2
INVENTION
The Appellants describe the invention at issue on appeal as follows.
The present invention . . . generat[es] and reus[es] subplans that
have all tautological predicates dropped. A tautological
predicate is one that returns all records when the query is
executed, which means it does not narrow the query. Thus,
tautological predicates may be dropped without affecting the
records returned when the query is executed. The subplans are
organized in the access plan cache under a single main plan,
which represents a query that includes all predicates . . . . By
creating subplans that have tautological predicates dropped, the
present invention avoids the overhead of rebuilding the access
plan each time a permutation of the query is run, and does not
suffer the performance penalties of using an access plan that is
grossly inefficient.
(Spec. 8.)

ILLUSTRATIVE CLAIM
1. An apparatus comprising:
at least one processor;
a memory coupled to the at least one processor;
a database table residing in the memory;
a query residing in the memory that references the database
table;
an access plan cache residing in the memory, the access plan
cache including:
a main access plan that corresponds to the query; and
at least one subplan that corresponds to the main
access plan, each subplan corresponding to a different
version of the query with at least one tautological
predicate removed; and
a query optimizer residing in the memory and executed by
the at least one processor, wherein the query optimizer analyzes
Appeal 2009-002478
Application 10/860,403

3
the query and determines whether a corresponding main access
plan and subplan exists for the query in the access plan cache,
and if so, the query optimizer uses the corresponding subplan to
execute the query.

REJECTION
Claims 1, 2, 4-7, 9-12, 14-20, 22, 23, 27-30, 34, and 35 stand rejected
under 35 U.S.C. 103(a) as being unpatentable over 2005/0097078 (Lohman)
and 2002/0143754 (Paulley).

CLAIMS 1, 7, 10-11, 17, 18, 20, 22, 30, AND 35
Based on the Appellants' arguments, we will decide the appeal of
claims 1, 7, 10-11, 17, 18, 20, 22, 30, and 35 based on claim 1 alone.
Regarding the representative claim, the Examiner finds that in Lohman's
¶ 0005 "queries are compiled and their query plans are saved in memory or
cache." (Ans. 19.) The Appellants argue that "[t]he examiner's assertion
that multiple access plans are stored in an access plan cache in Lohman is
not supported by this express teaching in Lohman which refers to storing a
single query execution plan in an in-memory cache during query
optimization." (Reply Br. 3.) Therefore, the issue before us is whether the
Examiner erred in finding that the combined teachings of Lohman and
Paulley, in combination with the prior art as a whole, would have suggested
storing multiple query access plans.

FINDINGS OF FACT
Lohman "relates to query optimization in database management
systems." (¶ 0003.) Paulley likewise "relates . . . to . . . query optimization
Appeal 2009-002478
Application 10/860,403

4
in a data processing system, such as a Database Management
System (DBMS)." (¶ 0004.)

ANALYSIS
"The test for obviousness is what the combined teachings of the
references would have suggested to one of ordinary skill in the art." In re
Young, 927 F.2d 588, 591 (Fed. Cir. 1991) (citing In re Keller, 642 F.2d
413, 425 (CCPA 1981)). In determining obviousness, furthermore, a
reference "must be read, not in isolation, but for what it fairly teaches in
combination with the prior art as a whole." In re Merck & Co., 800 F.2d
1091, 1097 (Fed. Cir. 1986) (citing Keller, 642 F.2d at 425). Regarding the
prior art as a whole, "'[e]very patent application and reference relies to some
extent upon knowledge of persons skilled in the art to complement that
[which is] disclosed . . . .'" In re Bode, 550 F.2d 656, 660 (CCPA 1977)
(quoting In re Wiggins, 488 F.2d 538, 543 (CCPA 1973)). Those persons
"must be presumed to know something" about the art "apart from what the
references disclose." In re Jacoby, 309 F.2d 513, 516 (CCPA 1962).
Here, Lohman explains that "[m]ost modern query optimizers
determine the best plan for executing a given [database] query by
mathematically modeling the execution cost for each of many alternative
Appeal 2009-002478
Application 10/860,403

5
QEPs [i.e., Query Execution Plans] and choosing the one with the cheapest
estimated cost." (¶ 0005.) Paulley includes the following similar disclosure.
[A] component called the optimizer determines the "plan" or
the best method of accessing the data to implement the SQL
[i.e., structured query language] query. The query optimizer is
responsible for transforming an SQL request into an access plan
composed of specific implementations of the algebraic operator
selection, projection, join, and so forth. Typically, this is done
by generating many different join strategies, evaluating the cost
of each, and selecting the access plan with the lowest overall
costs . . . .
(¶ 0012.)
Persons skilled in the art would have understood that to first model the
execution cost for many alternative access plans and to then choose the
access plan with the cheapest estimated cost would have suggested storing
the many alternative plans, at least temporarily, so that the cost of each could
be evaluated and then one of these plans chosen for use. Furthermore,
Lohman describes an in-memory cache for storing at least one access plan.
(¶ 0005.) Persons skilled in the art would have understood that such a cache
would have been used to store access plans temporarily. Based on the
aforementioned facts and analysis, we conclude that the Examiner did not
err in finding that the combined teachings of Lohman and Paulley, in
combination with the prior art as a whole, would have suggested storing
multiple query access plans.

CLAIMS 9, 19, AND 34
Based on the Appellants' arguments, we will decide the appeal of
claims 9, 19, and 34 based on claim 9 alone. Regarding the representative
claim, the Examiner finds that that the combined teachings of Lohman and
Appeal 2009-002478
Application 10/860,403

6
Paulley would have suggested automatically generating a plurality of access
plans that each corresponds to a query after dropping the at least one
tautological predicate. The Appellants argue that "neither Lohman nor
Paulley read[s] on automatically generating a plurality of access plans that
each correspond [sic] to the query after dropping the at least one tautological
predicate . . . ." (Reply Br. 10.) Therefore, the issue before us is whether the
Examiner erred in finding that the combined teachings of Lohman and
Paulley, in combination with the prior art as a whole, would have suggested
automatically generating a plurality of access plans that each corresponds to
a query after dropping the at least one tautological predicate.

FINDINGS OF FACT
"The improved normalization methodology of [Paulley's] invention
comprises a preprocessing phase and a normalization phase. The
preprocessing phase includes several steps that are designed to simplify the
original query expression, thereby simplifying the matrix processing
occurring in the normalization phase." (¶ 0076.)

ANALYSIS
"Non-obviousness cannot be established by attacking references
individually where the rejection is based upon the teachings of a
combination of references." Merck & Co., 800 F.2d at 1097 (citing Keller,
642 F.2d at 425).
Here, as explained regarding claim 1, we agree with the Examiner that
both Lohman and Paulley teach automatically generating a plurality of
access plans for a query. The latter reference, moreover, also teaches
Appeal 2009-002478
Application 10/860,403

7
"simplifyi[ng] [a query] expression by eliminating tautologies (statements
that are always true) . . . ." (¶ 0089.) The Appellants admit as much by
conceding that "Paulley is removing trivial tautologies and simplifying
tautological conditions . . . ." (Appeal Br. 15.)
The Examiner finds that the combination of these teachings would
have suggested automatically generating a plurality of access plans that each
corresponds to a query after dropping the at least one tautological predicate.
For their part, the Appellants merely argue that neither reference
individually "read on" the limitations at issue. Such an individual attack on
the references cannot establish non-obviousness. Based on the
aforementioned facts and analysis, we conclude that the Examiner did not
err in finding that the combined teachings of Lohman and Paulley, in
combination with the prior art as a whole, would have suggested querying
after dropping the at least one tautological predicate.

CLAIMS 2, 4-6, 12, 14-16, 23, AND 27-29
The Examiner finds that ¶ 0005 of "Lohman discloses checking for
executions plans (access plans) and picking the best plan (the one with the
least cost associated with it). Subplans would thus be also checked since
they would be query expressions which when compiled would become
execution plans. . . ." (Answer 6.) The Appellants argue that "[n]owhere
does Paulley teach dropping at least one tautological predicate from the
query, determining whether a corresponding access plan exists for the query
with the at least one dropped tautological predicate, and if so, the query
optimizer uses the corresponding access plan to execute the query." (Appeal
Br. 15.) Therefore, the issue before us is whether the Examiner erred in
Appeal 2009-002478
Application 10/860,403

8
finding that the combined teachings of Lohman and Paulley, in combination
with the prior art as a whole, would have suggested determining whether a
corresponding access plan exists for the query with the at least one dropped
tautological predicate and, if so, using the corresponding access plan to
execute the query.

ANALYSIS
"In rejecting claims under 35 U.S.C. § 103, the examiner bears the
initial burden of presenting a prima facie case of obviousness." In re
Rijckaert, 9 F.3d 1531, 1532 (Fed. Cir. 1993) (citing In re Oetiker, 977 F.2d
1443, 1445 (Fed. Cir. 1992)). "'A prima facie case of obviousness is
established when the teachings from the prior art itself would appear to have
suggested the claimed subject matter to a person of ordinary skill in the art.'"
In re Bell, 991 F.2d 781, 783 (Fed. Cir. 1993) (quoting In re Rinehart, 531
F.2d 1048, 1051 (CCPA 1976)).
Here, the Examiner's finding about ¶ 0005 of Lohman does not
address the claimed determining whether a corresponding access plan exists
for the query with the at least one dropped tautological predicate and, if so,
using the corresponding access plan to execute the query. Furthermore, we
agree with the Appellants that "when Paulley is removing trivial tautologies
and simplifying tautological conditions, Paulley is generating a new access
plan without regard to whether a corresponding access plan exists for the
query with the at least one dropped predicate." (Appeal Br. 15.)
Based on the aforementioned facts and analysis, we conclude that the
Examiner erred finding that the combined teachings of Lohman and Paulley,
in combination with the prior art as a whole, would have suggested
Appeal 2009-002478
Application 10/860,403

9
determining whether a corresponding access plan exists for the query with
the at least one dropped tautological predicate and, if so, using the
corresponding access plan to execute the query.

DECISION
We affirm the rejection of claims 1, 7, 9-11, 17-20, 22, 30, 34, and 35
but reverse the rejection of claims 2, 4-6, 12, 14-16, 23, and 27-29. No time
for taking any action connected with this appeal may be extended under 37
C.F.R. § 1.136(a)(1). See 37 C.F.R. § 1.136(a)(1)(v).

AFFIRMED-IN-PART

Erc

MARTIN & ASSOCIATES, LLC
P.O. BOX 548
CARTHAGE MO 64836-0548