Notice of Pre-AIA or AIA Status
The present application, filed on or after March 16, 2013, is being examined under the first inventor to file provisions of the AIA .
Claim Rejections - 35 USC § 102
The following is a quotation of the appropriate paragraphs of 35 U.S.C. 102 that form the basis for the rejections under this section made in this Office action:
A person shall be entitled to a patent unless –
(a)(1) the claimed invention was patented, described in a printed publication, or in public use, on sale or otherwise available to the public before the effective filing date of the claimed invention.
Claims 1-14, 25-26 are rejected under 35 U.S.C. 102(a) (1) as being unpatentable by Dantressangle et al (“Dantressangle” US 2012/0290608 A1), published on November 15, 2012.
As to claim 1, Dantressangle teaches “obtaining, by the database management system, a database expression in a database query for processing by the database management system, wherein the processing of the database query requires processing data stored in the database, and wherein the data stored in the database input matrix data and a second input matrix data” in paragraphs [0051-0055] (the SQL statement corresponding to a database expression; matrix multiplication corresponding to one or more input matrix-related operations that involves matrix A (is a table1 with key (or matrix ID) of 1000) and matrix B (table 1 with key (or matrix ID) of 2000) corresponding to two or more input matrices stored as data in the relational database; matrix A corresponding to a first matrix data and matrix B corresponding to a second matrix data).
Dantressangle teaches “in response to the database query, obtaining, by the database management system, at least partly based on the one or more physical properties of the obtained first input matrix data and the obtained second matrix data andobtained first matrix data, and a second input matrix data set as a disjointed subset of the obtained second input matrix data” in paragraphs [0051-0055] (A.value = 1 when A.I = 1 and A.J =1; A.value = 2 when A.I = 1 and A.J = 2; A.value = 3 when A.I = 2 and A.J = 1; …; A.value = 6 when A.I = 3 and A.J = 2; the first six values from value column of table 1 (corresponding to matrix ID = 1000) corresponds to a first matrix data set; the next 8 values after the sixth value from the value column of table 1 (corresponding to matrix ID = 2000) corresponds to a second matrix data set; table 1 data with matrix ID = 1000 correspond to the first matrix data; table 1 data with matrix ID = 2000 correspond to the second matrix data ).
Dantressangle teaches “wherein the determined first matrix data set is determined, by the database management system, at least partly based on a partitioning of the obtained first input matrix data into multiple partitions as two or more disjointed subsets, such that each one of the partitions of the obtained first matrix input data is a disjointed subset of the determined first matrix data, wherein the determined second matrix data set is determined, by the database management system, at least partly based on a partitioning of the obtained second input matrix data into multiple partitions as two or more disjointed subsets, such each one of the partitions of the obtained second matrix data is a disjointed subset of the obtained second input matrix data” in paragraphs [0051-0055] (noting that the first six values from value column of table 1 (corresponding to matrix ID = 1000) corresponds to a first matrix data set that is partitioned as a set of 3 disjointed subsets (fist disjointed subset is first two values of value column (1 and 2) where I values are 1; second disjointed subset comprises the next two values of value column (3 and 4); third disjointed subset comprises the next two values of value column (5 and 6)) ; the next 8 values after the sixth value from the value column of table 1 (corresponding to matrix ID = 2000) corresponds to a second matrix data set that is partitioned as a set of 2 disjointed subsets with of I value of 1 and I value of 2 respectfully).
Dantressangle teaches “in response to the database query, performing at least one matrix-related operation at least between each one the members of the determined first matrix data set and two or more of the members of the determined second matrix data set to determine ” in par. 0051 (the SQL statement of Sum (A.value * B.value) produces matrix multiplication result elements. Noting that matrix multiplication is implemented by SQL against a relational database; noting that matrix multiplication, in linear algebra, requires each and every element of the first matrix to multiply with each and every element of the second matrix in order to sum them up accordingly to produce the matrix result (please refer to how two matrices are multiplied in linear algebra)).
Dantressangle teaches “and determining, by the database management system, at least partly based on the one or more partial results, at least one output result for the database query as a result of the matrix-related operations involving the two or more input matrices of the obtained database expression” in par. 0055, table-2 (corresponding to at least one output result as a result of the matrix-related operations involving the two or more input matrices” in par. 0055, table-2 (corresponding to at least one output result as a result of the matrix-related operations involving the two or more input matrices; noting that table-2 contains columns I and J represented indices for a result matrix (the result of two matrix multiplication), column value represented the element values of the result matrix).
As to claim 25, it is rejected for similar to claim 1.
As to claim 26, it is rejected for similar to claim 1.
As to claim 2, Dantressangle teaches “optimizing the database query of the database by at least optimizing the performing of the one or more input matrix-related operations by at least the determining of the first matrix data set and the second matrix data set” in par. 0058 (single SQL query is optimized).
As to claim 3, Dantressangle teaches “wherein the relational database management system that includes multiple processors at least configured to operate in parallel” in par. 0005.
Dantressangle teaches “wherein the performing of the at least one matrix-related operation at least between each one the members of the first matrix data set and one or more of the members of the second matrix data set to obtain one or more partial results further comprises:
distributing, at least multiple matrix-related operations between the each one the members of the first matrix data set and one or more of the members of the second matrix data set, between the multiple processors configured at least to process the multiple matrix-related operations in parallel” in par. 0006 (process matrix operation in multiple processors).
As to claim 4, Dantressangle teaches “wherein the computer-implemented method further comprises: (a) distributing multiple members of the first matric data sets on each one of the multiple processors configured to process the multiple matrix-related operations in parallel; (b) combining a set of per-input data set member pairs on each one of the multiple processors by at least using a matrix-related operation to obtain a set of per-input data set member pair partial results on each one of the on each one of the multiple processors configured to process the multiple matrix- related operations in parallel; (c) distributing the set of partial results obtained on each one of the multiple processors between the multiple processors configured to process the multiple matrix- related operations in parallel; and (d) combining one or more partial results by at least using an additional matrix-related operation to obtain a final result” in paragraphs [0051-0055].
As to claim 5, it is rejected for similar reason as claim 4.
As to claim 6, Dantressangle teaches “The computer-implemented method of 1, wherein the at least one matrix Multiplication Related operation includes one or more of the following: a Matrix Multiply operation, and a Matrix Transpose operation” in par. 0051 (matrix multiplication operation).
As to claim 7, Dantressangle teaches “parsing a database query of the database as input, wherein the input database query includes the one or more input matrix-related operations involving two or more input matrices stored as data in the relational database” in paragraph [0051-0055] (SQL to perform matrix calculation on two matrix data stored in a relational database).
As to claim 8, Dantressangle teaches “wherein the database query is stated as at least one declarative statement in a database query language, and wherein the least one declarative statement includes at least one of the following provided as a database Multiplication-related operation for the database query language: a Matrix Multiply operation and a Matrix Transpose operation” in paragraph [0051-0055] (SELECT A.i, B.j , sum(A.value*B.value) corresponds to at least one declarative statement in a database query language; paragraphs [0052-0055] shows a database Multiplication-related operation for the database query language).
As to claim 9, Dantressangle teaches “verifying [[the]] correctness of the database query of the database that includes at least one matrix multiplication of the two or more matrices” in par. 0055, table 2.
As to claim 10, Dantressangle teaches “determining whether one or more tables and columns of the database that are named by the database query of the database exist with appropriate types; determining whether an expression associated with the database query of the database can be translated into a procedure consistent with an associated input database schema” in paragraphs [0060-0061].
As to claim 11, Dantressangle teaches “obtaining a database query by the database management system for processing by the database management system, wherein the database query requires at least one Matrix Multiply-Related operation involving at least the two or more matrices as input data from the data stored in the relational database; determining by the database management system how to process the database query by at least optimizing the least one Matrix Multiply operation” in par. 0058.
As to claim 12, Dantressangle teaches “Logical Optimization of the least one Matrix Multiply operation by at least determining one or more logical equivalent forms of at least a portion of the database query” in par. 0058 (SQL is rewritten in one or more logical equivalent SQL statement).
As to claim 13, Dantressangle teaches “wherein the logical optimization further comprises: combining one or more database relational operations (projection, selection, join, union, etc.) with one or more Matrix-Related operations including one or more of the following: a Matrix Transpose, a Matrix Multiply operation” in par. 0058 (select SQL statement is combined with matrix operation including matrix multiplication).
As to claim 14, Dantressangle teaches “wherein the logical optimization further comprises: determining an order of performing two or more multiply related operations by at least considering Matrix Algebra” in par. 0062 (algebraic operation can be leveraged at the matrix level to minimize internal relational database data movement).
Claim Rejections - 35 USC § 103
The following is a quotation of 35 U.S.C. 103 which forms the basis for all obviousness rejections set forth in this Office action:
A patent for a claimed invention may not be obtained, notwithstanding that the claimed invention is not identically disclosed as set forth in section 102 of this title, if the differences between the claimed invention and the prior art are such that the claimed invention as a whole would have been obvious before the effective filing date of the claimed invention to a person having ordinary skill in the art to which the claimed invention pertains. Patentability shall not be negated by the manner in which the invention was made.
Claims 15-24 are rejected under 35 U.S.C. 103 as being unpatentable over Dantressangle et al (“Dantressangle” US 2012/0290608 A1), published on November 15, 2012, and in further view of Zhang et al (“Zhang” US 2020/0372027 A1), published on November 26, 2020.
As to claim 15, it appears Dantressangle does not explicitly teach “wherein the optimizing the least one Matrix Multiply-Related operation further comprises: performing Physical Optimization of the least one Matrix Multiply Related operation by at least determining how to process a logical query plan for processing the database query of the database”.
However, Zhang teaches “wherein the optimizing the least one Matrix Multiply-Related operation further comprises: performing Physical Optimization of the least one Matrix Multiply Related operation by at least determining how to process a logical query plan for processing the database query of the database” in paragraphs [0006-0007] (“…generating, by the coordinator node, a second physical plan corresponding to the logical plan, and feeding back the second physical plan to the server node…”).
Dantressangle and Zhang are analogous art because they are in the same field of endeavor, database management. It would have been obvious to one of ordinary skill in the art before the effective filling date of the claim invention to optimize query (disclosed by Dantressangle) including “wherein the optimizing the least one Matrix Multiply-Related operation further comprises: performing Physical Optimization of the least one Matrix Multiply Related operation by at least determining how to process a logical query plan for processing the database query of the database”, as suggested by Zhang, in order to optimize database querying process (see Zhang par. 0007).
As to claim 16, Dantressangle teaches “wherein the performing of the Physical Optimization comprises one or more of the following: selecting one or more (low level) physical algorithms for processing of the least one Matrix Multiply Related operation; and selecting one or more data structures for processing the least one Matrix Multiply Related operation” in paragraphs [0032-0036].
As to claim 17, Dantressangle teaches “provisioning or reserving one or more physical compute resources of the database management system, wherein the one or more physical compute resources of the database management system include: CPU time, memory, temporary storage space, and network bandwidth” in par. 0032.
As to claim 18, Dantressangle teaches “blocking and partitioning of first data of at least the first matrix by at least: (i) determining one or more block sizes for the first data, and (ii) partitioning of the first data into data blocks according to the determined block size” in paragraphs [0044-0047].
As to claim 19, Dantressangle teaches “distributing the data blocks to multiple processors of the database management system for parallel processing by the multiple processors” in par. 0032.
As to claim 20, Dantressangle teaches “selecting one or more low-algorithms for performing a single computer calculation” in par. 0032.
As to claim 21, Dantressangle teaches “distributing all of data blocks of the first and second input matrices to a single processor of multiple processors of the database management system where a final result is to be computed; creating copies of all of the data blocks for the first input matrix on all of the processors the database management system while distributing a subset of data blocks of the second input matrix to different processors of the multiple processors to compute a per-processor local result that is a portion of the final result before combining per-processor portions into the final result; and distributing a subset of the data blocks of a first input matrix to each of the processors of the multiple processors while distributing a subset of data blocks for the second input to each processor to compute a per-processor local result before iteratively redistributing or moving blocks of both input matrices among the multiple processors until the complete set of block-wise partitions is calculated, and thereafter combining the per-processor portions into one or more final results” in paragraphs [0031-0032].
As to claim 22, Dantressangle teaches “storing the data of the two or more matrices in the relational database in a pre- processed form that is configured for performing the matrix-related operation” in paragraphs [0019-0020].
As to claim 23, Dantressangle teaches “storing data in a manner in a pre-partitioned for processing of the matrix-related operation; and storing data of at least the first matrix data in accordance with one or more encodings (storing data in a space-efficient manner", or "organizing data from input matrices into blocks suitable for calculations)” in paragraphs [0019-0020].
As to claim 24, Dantressangle teaches “wherein the determining of first matrix data set and the second matrix data set is determined at least partly based on one or more sizes of one more cache memory of the one or more processors” in par. 0031.
Response to Arguments
Regarding Applicant’s argument, on page 7 of the remarks, Applicant argues that the office action only asserted that the disjoined data subsets would be the matrix itself. Applicant’s argument is respectfully considered, but is not persuasive. According to paragraphs [0051-0055] of Dantressangle’s, the matrix multiplication process shows that A.value = 1 when A.I = 1 and A.J =1, A.value = 2 when A.I = 1 and A.J = 2, A.value = 3 when A.I = 2 and A.J = 1, …, A.value = 6 when A.I = 3 and A.J = 2. The first six values from value column of table 1 (corresponding to matrix ID = 1000) corresponds to a first input matrix data set. It’s emphasized that “the first six values from value column of table 1” (not the whole matrix A). The next 8 values after the sixth value from the value column of table 1 (corresponding to matrix ID = 2000) corresponds to a second input matrix data set. It’s emphasized that “the next 8 values after the sixth value from the value column of table 1” (not the whole matrix B). Table 1 data with matrix ID = 1000 correspond to the first matrix data; table 1 data with matrix ID = 2000 correspond to the second matrix data.
Regarding Applicant’s argument, on page 13 of the remarks, Applicant argues “As such, it is apparent that Dantressangle does NOT teach partitioning, by a database system, each one of two or more obtained input matrices in a database expression, into multiple disjointed data sets, and then performing at least one matrix-related operation at least between each one the members of the first matrix data set and two or more of the members of the second matrix data set to obtain one or more partial results, such that the at least one matrix-related operation includes a matrix Multiplication Related operation”. Applicant’s argument is respectfully considered, but is not persuasive. During the matrix multiplication process, each row in a first input data set of matrix A is partitioned in order to multiply with each column in a second input data set of matrix B in order to produce result element values of the multiplication result.
Regarding Applicant’s argument, on page 14 of the remarks, Applicant argues “Furthermore, it is respectfully submitted that the language of claim 1 is clear and concise by at least requiring: "performing at least one matrix-related operation at least between each one the members of the first matrix data set and two or more of the members of the second matrix data set to obtain one or more partial results, wherein the at least one matrix-related operation includes a matrix Multiplication Related operation" (claim 1, emphasis added). The Examiner has the burden to show that that Paragraphs [0051] of Dantressangle teaches the claimed features”. Applicant’s argument is respectfully considered, but is not persuasive. In par. 0051, the SQL statement of Select A(i), B(i), Sum (A.value * B.value) produces matrix multiplication result elements. It is noted that to implement matrix multiplication, the SQL statement above is executed by letting i, j traversed to cover every element in matrix A and matrix B. For every fix value of i and j, the corresponding A.value and B.value are determined to provide the Sum of (A.value * B.value) as each element value forming the result matrix.
Regarding Applicant’s argument, on page 14 of the remarks, Applicant argues that Dantressangle does not teach the arrangement of the claim elements. Applicant’s argument is respectfully considered, but is not persuasive. Paragraphs [50-55] shows the order of matrix multiplication as described in the claim language.
Conclusion
The prior art made of record and not relied upon is considered pertinent to applicants’ disclosure:
. Collins et al (US 2011/0295838 A1)
. Bayliss et al (US 2007/0208694 A1)
. Lipman (US 10621235 B1)
THIS ACTION IS MADE FINAL. See MPEP § 706.07(a). Applicant is reminded of the extension of time policy as set forth in 37 CFR 1.136(a).
A shortened statutory period for reply to this final action is set to expire THREE MONTHS from the mailing date of this action. In the event a first reply is filed within TWO MONTHS of the mailing date of this final action and the advisory action is not mailed until after the end of the THREE-MONTH shortened statutory period, then the shortened statutory period will expire on the date the advisory action is mailed, and any extension fee pursuant to 37 CFR 1.136(a) will be calculated from the mailing date of the advisory action. In no event, however, will the statutory period for reply expire later than SIX MONTHS from the date of this final action.
Any inquiry concerning this communication or earlier communications from the examiner should be directed to Loc Tran whose telephone number is (571)272-8485. The examiner can normally be reached on Mon - Fri (8:00 am - 5:00 pm).
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, Amy Ng can be reached on 571-272-3676. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300. Information regarding the status of an application may be obtained from the Patent Application Information Retrieval (PAIR) system. Status information for published applications may be obtained from either Private PAIR or Public PAIR. Status information for unpublished applications is available through Private PAIR only. For more information about the PAIR system, see http://pair-direct.uspto.gov. Should you have questions on access to the Private PAIR system, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative or access to the automated information system, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/LOC TRAN/
Primary Examiner, Art Unit 2164