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 .
DETAILED ACTION
This Office Action is in response to a Non-Provisional Patent Application received on 03/17/2025. In the application, claims 1-20 have been received for consideration and have been examined.
Specification
Applicant’s submitted specification has been reviewed and found to be in compliance.
Drawings
Applicant’s submitted drawings have been reviewed and found to be in compliance.
Claim Rejections - 35 USC § 103
In the event the determination of the status of the application as subject to AIA 35 U.S.C. 102 and 103 (or as subject to pre-AIA 35 U.S.C. 102 and 103) is incorrect, any correction of the statutory basis (i.e., changing from AIA to pre-AIA ) for the rejection will not be considered a new ground of rejection if the prior art relied upon, and the rationale supporting the rejection, would be the same under either status.
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, 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.
Claim(s) 1-4, 8-11, and 15-18 are rejected under 35 U.S.C. 103 as being unpatentable over Lilly et al. (US20200380159A1) in view of Ngo et al. (US20250005194A1).
Regarding claim 1, Lilly discloses:
a computer-implemented method comprising identifying a SQL query, wherein a computing system obtains or receives SQL query 112 and translates the SQL query into a modified SQL query incorporating a privacy mechanism. See Lilly, Fig. 3 and corresponding disclosure (¶[0053-0059]). Lilly further teaches that the modified query may produce a differentially private query result.
Regarding “identifying one or more source tables against which the SQL query will be processed and a classification of each source table,” Lilly teaches that an SQL database contains one or more tables, that relations may be represented as tables, and that the SQL query operates against such database data. During recursive translation, Lilly iterates over each range (relation or query) of a SELECT statement and builds an associative map. See Lilly, Phase 3.1 (¶[0072]).
Lilly does not expressly teach the claimed classification of each source table.
Ngo, however, teaches that its SQL engine receives (a) a query statement, (b) privacy policies associated with the datasets being queried, and (c) a schema for each dataset/table and dataset locations. Ngo further teaches that the privacy limitations may differ between datasets. See Ngo, ¶[0011]/Fig. 2 and claim 1.
It would have been obvious to one of ordinary skill to associate the privacy classification/policy information taught by Ngo with the source tables identified by Lilly so that the privacy characteristics of the data can be determined during Lilly's privacy-enhancing query transformation.
Regarding “generating a parse tree based on the SQL query, the parse tree comprising the one or more source tables, an output table, and at least one operation,” Lilly expressly teaches parsing the SQL query to produce a parse tree in Phase 2, followed by recursively translating that parse tree. See Lilly, Phases 2 ¶[0071] and 3 ¶[0072-0076].
Ngo additionally teaches parsing the SQL statement into an SQL AST, explaining that an AST is a structured tree and that, for SQL, the tree may contain Join, Filter, Projection, etc. nodes. See Ngo, ¶[0011].
Regarding “searching the parse tree for operations to re-write by: selecting a current branch to search,” Lilly teaches recursively translating the parse tree, iterating over ranges/relations or queries in a SELECT statement, and recursively processing the parse tree associated with each target. See Lilly, Phases 3.1–3.2 ¶[0071-0076].
Regarding “performing, as an analyzed operation, an analysis of each operation in the current branch starting at the output table and for each operation,” Lilly teaches iterating over the target list of the SELECT statement and, for each target, recursively walking its parse tree to identify protected attributes and aggregation operations. See Lilly, Phase 3.2 and Fig. 6.
Regarding “determining whether the analyzed operation is an aggregation process that transforms a user-level detailed table (ULDT) into an aggregate table,” Lilly teaches that an aggregate SQL query produces summaries of grouped data and teaches determining, while recursively traversing the parse tree, whether a protected attribute occurs as an argument to an aggregate operation. Lilly expressly identifies supported aggregate operations and transforms such aggregate expressions.
Ngo additionally teaches distinguishing underlying private data from releasable aggregate information. In particular, Ngo teaches privacy restrictions requiring aggregation and modifying a logical query plan to calculate counts of distinct rows contributing to aggregation groups, with rows/groups failing privacy thresholds being excluded.
Thus, Lilly in view of Ngo teaches or suggests determining whether an operation transforms protected/detailed source information into aggregate information.
Regarding:
“in response to the operation being an aggregation process that transforms a ULDT into an aggregate table: re-writing the operation with a differential privacy (DP) operation”
Lilly expressly teaches recursively translating the parse tree by replacing standard SQL aggregates with references to results from a subquery Q. Lilly further teaches computing aggregate estimates from a noisy histogram such that the resulting computations remain differentially private. See Lilly, Phases 3–5.
Lilly specifically explains that the SQL query is transformed so that, rather than being evaluated directly over the database, the result is computed from a noisy histogram and that calculations performed from the differentially private noisy object remain differentially private.
Regarding:
“in response to the operation not being an aggregation process that transforms a ULDT into an aggregate table: proceeding to the next operation in the current branch”
Lilly teaches iteratively and recursively walking the parse tree, examining targets and protected attributes to determine whether they occur in supported aggregate operations. Processing continues through the remaining portions of the tree when the currently examined element does not require replacement. See Lilly, Phase 3.2 and Fig. 6.
It would have been obvious to proceed to the next operation when the presently analyzed operation does not satisfy the rewrite condition because doing so is necessary to complete Lilly's recursive traversal and identify subsequent operations requiring privacy treatment.
Regarding “selecting a next branch as the current branch; and repeating the analysis until each branch of the parse tree has been searched,” Lilly teaches recursively processing the parse tree, including recursively processing ranges that themselves constitute queries/subqueries and iterating over each range and target. See Lilly, Phases 3.1–3.2.
Accordingly, Lilly in view of Ngo renders claim 1 obvious.
It would have been obvious to one of ordinary skill to combine Ngo's dataset-specific privacy policies with Lilly's privacy-enhancing SQL transformation because both references concern enforcing privacy requirements during SQL query processing. Lilly transforms parsed SQL to incorporate a privacy mechanism before execution, whereas Ngo associates privacy requirements with individual datasets and rewrites an SQL AST according to those requirements.
The combination would predictably allow Lilly's transformation process to determine from the source-table privacy characteristics whether a particular operation involving that data requires privacy treatment.
Regarding claim 8, it is a computer-readable storage medium claim and recites similar subject matter as claim 1 and therefore rejected under similar ground of rejection.
Regarding claim 15, it is a computer-implemented system claim and recites similar subject matter as claim 1 and therefore rejected under similar ground of rejection.
Regarding claim 2, the combination of Lilly and Ngo discloses:
The method of claim 1, wherein the classification of each source table indicates whether each source table is a ULDT or an aggregate table (Ngo teaches associating privacy policies and schemas with individual datasets/tables and using such privacy policies during structural transformation of the query AST. Ngo additionally distinguishes underlying rows/private data from aggregate groups and expressly modifies the logical plan to calculate counts of distinct rows contributing to aggregation groups.
Lilly similarly distinguishes database records containing individual information from aggregate SQL queries that summarize grouped data and applies its privacy mechanism to aggregates over protected information).
It would have been obvious to classify each source table according to whether it contains user-level detailed data or aggregate data because that classification indicates whether subsequent aggregation of the table requires Lilly's differential-privacy treatment.
Regarding claim 9, it is a computer-readable storage medium claim and recites similar subject matter as claim 2 and therefore rejected under similar ground of rejection.
Regarding claim 16, it is a computer-implemented system claim and recites similar subject matter as claim 2 and therefore rejected under similar ground of rejection.
Regarding claim 3, the combination of Lilly and Ngo discloses:
The method of claim 1, wherein the parse tree comprises at least one intermediate table, wherein an intermediate table is a result of an operation that is not the output table (Lilly expressly teaches recursively translating the parsed SQL into an intermediate SQL query. Lilly further teaches replacing standard SQL aggregate expressions with references to results generated by a subquery Q and subsequently compiling the intermediate SQL query into the modified SQL query. See Lilly, Fig. 4 and Phases 3–5.
Ngo similarly transforms the SQL AST into a logical plan and generates physical plans for the underlying datasets).
It would have been obvious for the query/parse tree to contain an intermediate relational result produced by an operation and subsequently consumed in producing the final output.
Regarding claim 10, it is a computer-readable storage medium claim and recites similar subject matter as claim 3 and therefore rejected under similar ground of rejection.
Regarding claim 17, it is a computer-implemented system claim and recites similar subject matter as claim 3 and therefore rejected under similar ground of rejection.
Regarding claim 4, the combination of Lilly and Ngo discloses:
The method of claim 1, comprising generating a tag for each table in the parse tree according to a set of tagging rules (Lilly teaches building an associative map for the ranges/relations encountered during recursive traversal of the parse tree, while Ngo teaches associating privacy policies and schema information with the respective queried datasets and using those characteristics to structurally transform the AST.
It would have been obvious to represent the determined privacy classification associated with each table as a tag or equivalent machine-readable metadata value associated with the corresponding table node. Applying predetermined tagging rules would predictably permit the privacy classification to be maintained while traversing the query tree and determining whether downstream operations require privacy treatment).
Regarding claim 11, it is a computer-readable storage medium claim and recites similar subject matter as claim 4 and therefore rejected under similar ground of rejection.
Regarding claim 18, it is a computer-implemented system claim and recites similar subject matter as claim 4 and therefore rejected under similar ground of rejection.
Claim(s) 5-6, 12-13, and 19-20 are rejected under 35 U.S.C. 103 as being unpatentable over Lilly et al. (US20200380159A1) in view of Ngo et al. (US20250005194A1) and further in view of Rogers et al., (US20180096166A1).
Regarding claim 5, the combination of Lilly and Ngo discloses:
Regarding “for each source table classified as a ULDT, set the tag equal to zero; [and] for each source table classified as an aggregate table, set the tag equal to one,” Rogers teaches assigning discrete security labels, such as low and high, to query-plan phrases based upon the sensitivity of the associated information. Rogers further teaches an annotated schema specifying the protection required by source attributes.
In view of Ngo's table-specific privacy information and Lilly's distinction between detailed protected data and aggregated results, it would have been obvious to represent the respective classifications using numerical tags. The particular selection of 0 and 1 would have been a predictable numerical encoding of the respective classification states.
Regarding:
“for each intermediate or output table that is a result of a JOIN or UNION operation, set the tag equal to a minimum tag value of input tables used in the JOIN or UNION operation”
Rogers expressly teaches that joins and set operations combine information from multiple inputs and execute at the level of their most sensitive inputs. Rogers's r-nest-bin rule further provides that where a binary operator such as a join or set operation has at least one high child, the resulting operator is judged high.
Rogers additionally teaches determining the protection level of output columns by taking the maximum security policy of their source attributes.
Where the numerical encoding is arranged such that the lowest numerical tag represents the most sensitive/user-level data—for example, claim 5's 0 representing ULDT—the known “most sensitive input controls” rule taught by Rogers would be implemented numerically by:
output tag = MIN(input tags).
Choosing MIN rather than MAX is therefore a consequence of the selected numerical ordering rather than a materially different information-flow rule.
Regarding:
“for each intermediate or output table that is a result of an aggregation operation that does not group by identity fields, set the tag equal to the tag value of an input table incremented by two”
Rogers expressly treats aggregation as an operator having an operation-specific security typing rule (r-aggregate) and teaches propagation of security classification through the query tree. Rogers states that aggregation, distinct, join, set operations, and sort operate according to the sensitivity of their input expressions.
Lilly further teaches that aggregation changes detailed protected records into summarized grouped information and applies differential-privacy processing to the resulting aggregate.
It would have been obvious to reflect the known transition from detailed user-level information to a distinct aggregate privacy state by changing the associated numerical classification tag. Once ordinal numerical values are selected to represent successive privacy/aggregation states, incrementing the tag provides a predictable mechanism for recording that transformation.
However, neither Rogers nor Lilly expressly teaches the particular arithmetic increment of exactly “two.” The +2 limitation therefore rests on the obviousness of the numerical encoding rather than an express disclosure in Rogers.
Regarding:
“for each intermediate or output table that is not a result of an aggregation operation that does not group by identity fields, set the tag equal to the input tag”
Rogers teaches that subsequent operators are typed according to their source nodes and that operators which do not introduce a more restrictive condition may execute at the same security level as the child/source operation. Rogers specifically explains that project and limit operations reveal no additional information and may retain the security classification of the source operator.
Thus, Rogers teaches propagating an existing classification through query-tree operations where the relevant privacy/sensitivity state is unchanged.
It would have been obvious to incorporate Rogers's security-label propagation into Lilly/Ngo because Rogers addresses the same problem of tracking privacy/security characteristics as information flows through an SQL operator tree. Rogers expressly teaches bottom-up traversal, labels for query-plan nodes, operation-specific rules, and propagation of the most sensitive classification through JOIN and set operations.
Applying Rogers's known information-flow mechanism to the Lilly/Ngo system would predictably allow the privacy classification associated with source tables to be propagated to intermediate and output tables so that Lilly's system could identify the operation at which detailed information becomes aggregate.
Regarding claim 12, it is a computer-readable storage medium claim and recites similar subject matter as claim 5 and therefore rejected under similar ground of rejection.
Regarding claim 19, it is a computer-implemented system claim and recites similar subject matter as claim 5 and therefore rejected under similar ground of rejection.
Regarding claim 6, the combination of Lilly, Ngo and Rogers discloses:
The method of claim 5, wherein determining whether the analyzed operation is an aggregation process that transforms a ULDT into an aggregate table comprises: determining whether the analyzed operation receives an input table with a tag value of zero and produces an output or intermediate table with a tag value of two (input table tag = 0, andoutput/intermediate table tag = 2.
Lilly teaches determining whether a protected attribute is subjected to an aggregate operation and modifying qualifying aggregate operations to provide differential privacy.
Rogers teaches bottom-up propagation of security classifications through the operator tree according to operation-specific rules, including a specific r-aggregate rule.
Under the tagging scheme applied to claim 5, a ULDT receives tag 0, while the qualifying aggregation changes the privacy classification by the specified increment: 0 + 2 = 2).
It would have been obvious to detect the ULDT-to-aggregate transition by determining whether an operation receives the ULDT classification (0) and produces the corresponding aggregate classification (2). Doing so constitutes the predictable use of the already-generated metadata to identify the transformation for which Lilly applies privacy-enhancing processing.
Regarding claim 13, it is a computer-readable storage medium claim and recites similar subject matter as claim 6 and therefore rejected under similar ground of rejection.
Regarding claim 20, it is a computer-implemented system claim and recites similar subject matter as claim 6 and therefore rejected under similar ground of rejection.
Claim(s) 7, and 14 are rejected under 35 U.S.C. 103 as being unpatentable over Lilly et al. (US20200380159A1) in view of Ngo et al. (US20250005194A1) and further in view of Chinchwadkar et al., (US20080114803A1) hereinafter referred as Chin.
Regarding claim 7, the combination of Lilly and Ngo discloses:
The method of claim 1, wherein generating the parse tree based on the SQL query comprises sending the SQL query to a query engine with instructions to parse the SQL query and return the parse tree without executing the SQL query (Lilly expressly teaches parsing an SQL query to produce a parse tree before recursively translating the parsed query and before sending the resulting modified SQL query to the SQL database for execution. See Lilly, Fig. 4 and Phases 2–3.
Ngo similarly teaches using an SQL parser/optimizer, such as Spark Catalyst, and parsing an SQL statement into an AST before structural transformation and subsequent generation of physical plans).
Lilly and Ngo do not expressly teach instructing a query engine to return the parse tree without executing the query,
Chin teaches that a conventional database query engine includes distinct parser, normalization/rewrite, optimizer/compiler, and execution-engine components. The parser converts query text into a query tree; the tree is thereafter normalized and optimized; and only subsequently does the execution engine execute the resulting plan.
Chin specifically teaches that SQL statements are passed to parser 261, which converts them into a query tree, after which the query tree is passed to normalizer 263 and compiler 265. Execution is separately performed by execution unit 269 (Chin: [0064]).
It would have been obvious to one of ordinary skills to use this known parser interface to obtain the query tree without executing the original SQL query, because Lilly specifically requires analysis and modification of the parse tree before the privacy-modified query is forwarded to the database for execution. Executing the original unmodified query would defeat Lilly's stated objective of incorporating the privacy mechanism before the query reaches the database.
Regarding claim 14, it is a computer-readable storage medium claim and recites similar subject matter as claim 7 and therefore rejected under similar ground of rejection.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to SYED M AHSAN whose telephone number is (571)272-5018. The examiner can normally be reached 8:30 AM - 6:00 PM.
Examiner interviews are available via telephone, in-person, and video conferencing using a USPTO supplied web-based collaboration tool. To schedule an interview, applicant is encouraged to use the USPTO Automated Interview Request (AIR) at http://www.uspto.gov/interviewpractice.
If attempts to reach the examiner by telephone are unsuccessful, the examiner’s supervisor, William Korzuch can be reached at 571-272-7589. The fax phone number for the organization where this application or proceeding is assigned is 571-273-8300.
Information regarding the status of published or unpublished applications may be obtained from Patent Center. Unpublished application information in Patent Center is available to registered users. To file and manage patent submissions in Patent Center, visit: https://patentcenter.uspto.gov. Visit https://www.uspto.gov/patents/apply/patent-center for more information about Patent Center and https://www.uspto.gov/patents/docx for information about filing in DOCX format. For additional questions, contact the Electronic Business Center (EBC) at 866-217-9197 (toll-free). If you would like assistance from a USPTO Customer Service Representative, call 800-786-9199 (IN USA OR CANADA) or 571-272-1000.
/SYED M AHSAN/Primary Examiner, Art Unit 2491
Prosecution Insights