Ex Parte Abdo

Board of Patent Appeals and Interferences

Mar 15, 2010

10230640 (B.P.A.I. Mar. 15, 2010)

UNITED STATES PATENT AND TRADEMARK OFFICE
____________
BEFORE THE BOARD OF PATENT APPEALS
AND INTERFERENCES
____________
Ex parte ABDO ESMAIL ABDO
____________
Appeal 2009-002908
Application 10/230,6401
Technology Center 2100
____________
Decided: March 15, 2010
____________
Before LEE E. BARRETT, JOSEPH L. DIXON, and STEPHEN C. SIU,
Administrative Patent Judges.

BARRETT, Administrative Patent Judge.

DECISION ON APPEAL
This is a decision on appeal under 35 U.S.C. § 134(a) from the final
rejection of claims 1-18. We have jurisdiction pursuant to 35 U.S.C. § 6(b).
We affirm-in-part.

1 Filed August 29, 2002, titled "Estimation of Input/Output
Requirements for Table Probe in Join Processing." The real party in interest
is International Business Machines Corporation.
Appeal 2009-002908
Application 10/230,640

2
STATEMENT OF THE CASE
The invention
The invention relates to generating a statistic for a join operation
directed to an inner and an outer relation of a database. A database table
(otherwise known as a relation) includes columns (otherwise known as
attributes) and rows (otherwise known as tuples). For example, the table of
Figure 1 identifies vehicle owners by name and city, and the make, model,
model year, and other information about their vehicles. Spec. 1, l. 15 to
Spec. 2, l. 10. One form of query is a join, which uses the content of one
table to identify attributes of interest in another. For example, the table of
Figure 2A identities high schools attended by various individuals. A join of
the tables in Figures 1 and 2A may be used to identify the cars driven by
students of, say, the "Lincoln" high school. To perform the join, those tuples
in the table of Figure 2A having a high school value of "Lincoln" must be
retrieved, and then used to probe the table of Figure 1 for tuples that have a
matching surname and given name. Spec. 2, ll. 12-22.
In each join operation, there are two tables, the "outer" table, from
which tuples are to be retrieved, and the "inner" table, which is probed for
matching tuples. Spec. 3, ll. 5-7.
A join operation is likely to require an extensive number of
operations, and the efficiency with which the operation is completed may
vary dramatically based on the manner in which joins are performed, e.g.,
the amount of memory allocated for the join operation, the order in which
values from the outer table are probed in the inner table, and, in the case of a
Appeal 2009-002908
Application 10/230,640

3
multiple join operation, the order in which the operations are performed.
Spec. 3, ll. 11-16. Various methods have been used for estimating the
complexity, i.e., the computational cost, of a join operation. Spec. 3,
ll. 17-18. These methods, however, are often inaccurate because they do not
account for the way in which data is stored in the physical implementation of
the relational database system. Spec. 3, l. 23 to Spec. 4, l. 2.
The invention relates to costing a join operation by costing the
input/output operations (disk swaps) that are inherent in the retrieval of
tuples from the inner and outer tables. Because an entire database cannot
typically be held in memory, memory is typically used to hold indices and
other structures that are useful in responding to queries, and hold some pages
of data, which are swapped from the hard disk as part of retrievals. Spec. 4,
ll. 9-17. One factor the affects the speed of response to a query is the
number of swaps between memory and disk. Because tuples are typically
randomly ordered in the outer and inner tables, as each matching tuple in the
inner table is retrieved, the data on disk for the inner table will be randomly
accessed, which raises the possibility that pages of the inner table will be
swapped from memory multiple times. If this were to occur to an excessive
amount, then processing could be done more efficiently by collecting the
pointers to all matching tuples in the inner table, sorting the pointers (so that
all data on the same page is accessed at the same time), and then accessing
the data in the inner table sequentially. However, sorting the pointers takes
computing resources, so sorting should only be done if the increased
efficiency outweighs the increased consumption of resources. The
Appeal 2009-002908
Application 10/230,640

4
Specification describes a method whereby it can be determined whether the
data in the inner table of a join can be more efficiently accessed by
collecting and sorting pointers to that data prior to accessing the data.
Spec. 5, l. 12 to Spec. 6, l. 3. In particular, the Specification describes a
specific computation of the number of input/output operations (disk swaps)
needed for a given data table, by modeling the retrieval of randomly
arranged data from that table. Spec. 6, ll. 14-16.

Illustrative claim
Claim 1 is reproduced below for illustration:

1. A computer-implemented method for generating a statistic to be
used in optimizing execution of a query, for a join operation directed
to an inner and an outer relation each comprising tuples, comprising

estimating in a computer processor a number of input/output
operations to an auxiliary storage device storing at least one said
relation required to retrieve tuples as part of performing said join
operation, based upon the arrangement of tuples within either or both
of said inner and outer relations.

The references

Chaudhuri US 5,598,559 Jan. 28, 1997

Paulley US 6,516,310 B2 Feb. 4, 2003
(filed Dec. 6, 2000)

The rejections
Claims 16 and 17 stand rejected under 35 U.S.C. § 101 as directed to
unpatentable subject matter. The Final Office Action (FOA) rejected
Appeal 2009-002908
Application 10/230,640

5
claims 1-5, 8-13, and 15-18 under § 101. The Examiner has withdrawn the
§ 101 rejection except as to claims 16 and 17. Ans. 8.
Claims 1-18 stand rejected under 35 U.S.C. § 103(a) as unpatentable
over Paulley and Chaudhuri.

35 U.S.C. § 101
Issue
Has Appellant shown that the Examiner erred in concluding that
claims 16 and 17 are directed to nonstatutory subject matter under
35 U.S.C. § 101?

Principles of law
"If a claim covers material not found in any of the four statutory
categories, that claim falls outside the plainly expressed scope of § 101 even
if the subject matter is otherwise new and useful." In re Nuijten,
500 F.3d 1346, 1354 (Fed. Cir. 2007). "A transitory, propagating signal . . .
is not a 'process, machine, manufacture, or composition of matter' [under
35 U.S.C. § 101]" and therefore does not constitute patentable subject matter
under § 101. Id. at 1357. Claims that are so broad that they read on
nonstatutory as well as statutory subject matter are unpatentable. Cf.
In re Lintner, 458 F.2d 1013, 1015 (CCPA 1972) ("Claims which are broad
enough to read on obvious subject matter are unpatentable even though they
also read on nonobvious subject matter.").

Appeal 2009-002908
Application 10/230,640

6
Findings of fact
Claim 16 recites a "program product for implementing a relational
database system" comprising "a relational database" and "relational database
software" and "a physical signal bearing media holding said relational
database and relational database software."
The Specification states:

Examples of signal bearing media include: recordable type media
such as floppy disks (e.g., a floppy disk) and CD ROMS, and
transmission type media such as digital and analog communication
links, including wireless communication links.

Spec. 9, ll. 9-13 (emphasis added).

Analysis
Appellant argues that claims 16-18 recite a program product held on a
"physical signal bearing media" and thus, "there is a tangible program
product recited." Br. 13.
The Final Office Action and Appellant's Brief were filed before
September 20, 2007, when In re Nuijten was decided by the Federal Circuit.
The Brief and the Examiner's Answer were filed before In re Bilski,
545 F.3d 943 (Fed. Cir. 2008), which deprecated the "useful, concrete and
tangible result" test of State St. Bank & Trust Co. v. Signature Fin. Group,
149 F.3d 1368 (Fed. Cir. 1998). Thus, Nuijten is the proper test for the
claims at issue, not the "useful, concrete and tangible result" test.
Nuijten holds that signals, even physical electrical signals in a wire,
are not patent eligible subject matter. Appellant's Specification discloses
Appeal 2009-002908
Application 10/230,640

7
that a "physical signal bearing medium" is broad enough to include a
communications link which transmits a transitory electrical signal and
therefore, we conclude that the Examiner was correct in rejecting claims 16
and 17. The Examiner correctly withdrew the rejection of claim 18, reciting
"the signal bearing media comprises a physical recordable media," which
requires a physical "manufacture" under § 101.

Conclusion
Appellant has not shown that the Examiner erred in concluding that
claims 16 and 17 are directed to nonstatutory subject matter under
35 U.S.C. § 101. The rejection of claims 16 and 17 is affirmed.

35 U.S.C. § 103(a)
Contentions
The Examiner finds that Paulley teaches the claimed subject matter
except for estimating the number of input/output operations required to
retrieve tuples as part of performing said join operation "based upon the
arrangement of tuples within either or both of said inner and outer relations."
FOA 4; Ans. 5. The Examiner finds that "Chaudhuri teaches that an
ordering of tuples of the table may be useful for the join (col. 9,
lines 43 - 48, Chaudhuri)." FOA 4; Ans. 5. The Examiner concludes that it
would have been obvious to apply the teaching of Chaudhuri to Paulley
because Paulley suggests that modifications may be made, Chaudhuri is
within the same field as Paulley, and the "combination would provide the
Appeal 2009-002908
Application 10/230,640

8
user more benefit in optimizing the queries using I/O estimation and the
ordering of the tuples in the table." FOA 5; Ans. 5.
Appellant argues that Chaudhuri describes that performing a group-by
operation at some intermediate point among several joins may have a lower
cost that performing the group-by operation after the joins and thus,
"Chaudhuri is thus not directed to a costing scheme that involves the
input/output operations to an auxiliary storage device, but rather a costing
scheme that is independent of such considerations." Br. 15.
The Examiner responds that Appellant is attacking the references
individually. The Examiner states that Paulley is used to teaching a costing
scheme that involve the input/output operations to an auxiliary storage
device. Ans. 9.
Appellant argues that "the Examiner is not explaining where the prior
art, separately or collectively, teaches that the input/output traffic required to
perform a join is or may be affected by the ordering of the tuples in the
relations involved." Br. 15.
The Examiner does not respond specifically to this argument.
Nevertheless, we do not assume the rejection is incorrect just because the
Examiner does not respond to the argument.
Appellant argues that "[t]he Examiner's assertion that it was 'well
known' or known from Chaudhuri to evaluate the ordering of tuples in a
relation, does not establish that it is known, in any way, that the ordering of
tuples affects the input/output operations for a join" (Br. 15) and without
such a disclosure, "there is nothing to support the Examiner's supposition
Appeal 2009-002908
Application 10/230,640

9
that the methodologies of Chaudhuri, which are directed to query ordering
when GROUP BY is used, should be redirected or reapplied in the very
different context of estimating input/output operations for a query"
(Br. 15-16).
The Examiner responds that Appellant is attacking the references
individually. Ans. 9-10. The Examiner states that Chaudhuri is based on
"cost estimation" and provides for "an ordering of tuples," which may be
useful for the join. Ans. 10. The Examiner finds that Paulley says that
modifications may be made without departing from its teachings and thus,
the ordering of tuples in Chaudhuri can be applied to Paulley, which is relied
upon for the "input/output operations." Ans. 10.

Issue
Has Appellant shown that the Examiner erred in concluding that the
references teach or suggest "estimating in a computer processor a number of
input/output operations to an auxiliary storage device storing at least one
said relation required to retrieve tuples as part of performing said join
operation" which is "based upon the arrangement of tuples within either or
both of said inner and outer relations," as recited in independent claim 1?
Independent claims 9 and 16 contain similar limitations, and thus, claim 1 is
treated as representative.

Principles of law
"[T]he test [for obviousness] is what the combined teachings of the
references would have suggested to those of ordinary skill in the art."
Appeal 2009-002908
Application 10/230,640

10
In re Keller, 642 F.2d 413, 425 (CCPA 1981). A rejection under 35 U.S.C.
§ 103(a) is based on the following factual determinations: (1) the scope and
content of the prior art; (2) the level of ordinary skill in the art; (3) the
differences between the claimed invention and the prior art; and (4) any
objective indicia of non-obviousness. KSR Int'l Co. v. Teleflex Inc.,
550 U.S. 398, 399 (2007) (citing Graham v. John Deere Co., 383 U.S. 1,
17-18 (1966)). All claim limitations must be taught or suggested.

Findings of fact
Paulley
Paulley describes:

A query "optimizer" in a relational DBMS is responsible for
transforming an SQL request into an access plan composed of specific
implementations of the algebraic operators selection, projection, join,
and so on. Typically, this is done by generating many different join
strategies, evaluating the cost of each, and selecting the access plan
with the lowest overall cost, where "cost" is a metric that measures a
combination of factors, including but not limited to the estimated
amount of computational overhead, number of physical I/O
operations, and response time. The process of generating these
alternative join strategies is termed "join enumeration."

Col. 2, ll. 31-42 (emphasis added).
Paulley further describes that "[c]ost estimation is an integral part of
the enumeration method, because it is through comparing the costs of partial
access plans that the ASA optimizer can quickly prune significant portions
of the join strategy search space." Col. 9, ll. 36-40.
Appeal 2009-002908
Application 10/230,640

11
Thus, Paulley teaches evaluating a cost of a join operation where the
cost can include the number of physical I/O operations, but, as noted by the
Examiner (FOA 4; Ans. 5), Paulley does not describe a cost estimate of the
number of input/output operations "required to retrieve tuples as part of
performing said join operation, based upon the arrangement of tuples within
either or both of said inner and outer relations," as recited in claim 1.

Chaudhuri
Chaudhuri describes a method of optimizing an SQL query having
"group-by" operators. Col. 1, ll. 14-16. (A "GROUP BY" operator is an
SQL clause for organizing and performing operations on information about
several different items to be aggregated.)
Chaudhuri describes that query execution is optimized in databases by
preprocessing the query to place it in a form which can be more efficiently
executed by the database system. Col. 1, ll. 20-22.
Chaudhuri describes that conventional approaches have failed to
optimize queries having group-by operators. The conventional approaches
perform the group-by operation after all join operations have been evaluated.
Col. 1, ll. 24-28.
Chaudhuri describes a method of optimizing an SQL query by
potentially transforming the query so that a "group-by" operator included in
the query is an internal node of the execution plan. An execution plan is a
specification for the order in which operations are performed in the
processing of a query. Col. 1, ll. 62-66.
Appeal 2009-002908
Application 10/230,640

12
The Examiner cites to the following portion of Chaudhuri as evidence
that ordering of tuples of the table may be useful for the join:
An interesting order is an ordering of tuples of the intermediate
relation that may be useful later either (a) if the ordering is the same
as that specified in a group-by clause of the query or (b) if the
ordering is useful in a future sort-merge join. The set (b) consists of
all future join columns.

Col. 9, ll. 43-48. The first sentence as well as following paragraphs relate to
the concept of an "interesting order."

Analysis
Initially, we agree with the Examiner's findings that Paulley generally
teaches (at col. 2, ll. 31-42) "estimating in a computer processor a number of
input/output operations to an auxiliary storage device storing at least one
said relation required to retrieve tuples as part of performing said join
operation," but does not teach that the estimate of the number of input/output
operations is "based upon the arrangement of tuples within either or both of
said inner and outer relations." The number of input/output operations in
Paulley could be estimated based on many factors that are unrelated to the
arrangement of tuples. The Examiner relies on Chaudhuri.
Chaudhuri describes cost estimation for a group-by join plan, i.e., a
plan for handling a query involving both "group-by" and "join" operations.
The cost estimate in Chaudhuri is concerned with placement of the group-by
operation relative to the join operations, not execution of the join operation.
For this reason, we agree with Appellant's argument that "Chaudhuri is thus
Appeal 2009-002908
Application 10/230,640

13
not directed to a costing scheme that involves the input/output operations to
an auxiliary storage device" (Br. 15).
The Examiner finds that "Chaudhuri teaches that an ordering of tuples
of the table may be useful for the join" (FOA 4; Ans. 5) because Chaudhuri
describes that an "interesting order" is "an ordering of tuples of the
intermediate relation that may be useful later either (a) if the ordering is the
same as that specified in a group-by clause of the query or (b) if the ordering
is useful in a future sort-merge join" (col. 9, ll. 43-47). Chaudhuri mentions
an "ordering of tuples," but we find no teaching or suggestion that the
ordering affects or is used to estimate the number of input/output operations,
so as to plausibly suggest a combination with Paulley to arrive at the claimed
invention. We agree with Appellant that there must be at least some
suggestion "that the ordering of tuples affects the input/output operations for
a join" (Br. 15) before there can be a suggestion that the number of
input/output operations in Paulley should be "based upon the arrangement of
tuples within either or both of said inner and outer relations."

Conclusion
Appellant has shown that the Examiner erred in concluding that the
references teach or suggest "estimating in a computer processor a number of
input/output operations to an auxiliary storage device storing at least one
said relation required to retrieve tuples as part of performing said join
operation, based upon the arrangement of tuples within either or both of said
Appeal 2009-002908
Application 10/230,640

14
inner and outer relations," as recited in claim 1. The rejection of claims 1-18
under 35 U.S.C. § 103(a) is reversed.

CONCLUSION
The rejection of claims 16 and 17 under 35 U.S.C. § 101 is affirmed.
The rejection of claims 1-18 under 35 U.S.C. § 103(a) is reversed.
Requests for extensions of time are governed by 37 C.F.R. § 1.136(b).
See 37 C.F.R. § 41.50(f).

AFFIRMED-IN-PART

rwk

IBM CORPORATION
ROCHESTER IP LAW DEPT. 917
3605 HIGHWAY 52 NORTH
ROCHESTER, MN 55901-7829