DETAILED ACTION
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 Objections
Claims 7, 17 are objected to because of the following informalities:
"wherein determining" should be "wherein the determining" [Claims 7, 17, lines 1, 1].
Appropriate correction is required. Further, in an effort to practice compact prosecution, each of these limitations has been interpreted similarly as in the provided recommendation for each limitation, above.
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-2, 5, 11-12, 15 are rejected under 35 U.S.C. 102(a)(1) as being anticipated by Houlihan (US 11,461,302).
Regarding claim 1, Houlihan discloses:
A method comprising: receiving a query for stored data items that have a plurality of attributes that include a first attribute and a second attribute that has a hierarchical relationship with the first attribute ([col. 9, lines 41-45] the facet schemas may also define a list of projected attributes, such as projected attributes 184 and 194. In some embodiments, the projected attributes may be a subset of the attributes contained in the primary item instance 170 [col. 17, lines 8-21] The process of FIG. 10A illustrates an insert operation where the insert request specifies alternate keys for an item. The process begins at operation 1010, where a request is received from a client to insert an item into a table. The request may specify a first key for the item and a set of other keys for the item. In some embodiments, the first key may be an attribute of the item to be used as a partition key or sort key for a primary instance of the item. In some embodiments, the set of second keys may be alternative partition keys attributes or sort key attributes to be used for secondary instances of the item. In some embodiments, the insert request may specify a set of facet schemas, including a primary facet schema and a secondary facet schema, as shown in FIG. 2B);
performing a first sort of the stored data items based on a first set of ordering keys, the first set of ordering keys including the first attribute and the second attribute; performing a second sort of the stored data items based on a second set of one or more ordering keys, the second set being a proper subset of the first set and including the second attribute as an ordering key; generating a first sorted structure of the second sort of the stored data items inserting first pointers into the first sorted structure, where the first pointers point to the stored data items; generating a second sorted structure of the second sort of the stored data items; and inserting second pointers into the second sorted structure, where the second pointers point to the stored data items ([col. 3, lines 7-9] When items are inserted into a table or a collection a pointer to that item is maintained for each attribute that is being indexed [col. 17, lines 24-44] At operation 1012, the primary instance of the item is created according to the first key. In some embodiments, the creation may involve modifying the insert request to be sent to storage nodes. In some embodiments, the creation may create a data representation of the primary instance to be inserted. In some embodiments, the creation involves copying attribute values of specified attributes in the item, according to the primary facet schema, into one or more overloaded key fields in the primary instance. In some embodiments, the primary instance has an overloaded partition key field and an overloaded sort key field. At operation 1014, the primary instance is stored in the table according to the first key. In some embodiments, a request router node may send the primary instance to a partition group of the table to be stored. In some embodiments, the table is divided into a number of partitions, each managed by a group of storage nodes. In some embodiments, the primary instance is assigned to a partition group according to the value of its partition key. In some embodiments, the primary instance is stored in the partition in a sorted order according to the value of its sort key [cols. 17-18, lines 59-13] At operation 1022, a secondary instance of the item is created according to a second key from the set of other keys. In some embodiments, the second key may be an item attribute to be used as an alternate partition key or alternate sort key of the secondary instance. The second key may be defined in a secondary facet schema specified in the insert request. In some embodiments, the creation may involve modifying the insert request to be sent to storage nodes or creating a data representation of the secondary instance to be inserted. In some embodiments, the creation involves copying attribute values of specified attributes in the item, according to the secondary facet schema, into one or more overloaded key fields in the secondary instance. At operation 1024, the secondary instance is stored in the table according to the second key. In some embodiments, the request router node may send the secondary instance to a partition group of the table to be stored. In some embodiments, the secondary instance is assigned to a partition group of the table according to the value of its partition key. In some embodiments, the secondary instance is stored in the partition in a sorted order according to the value of its sort key);
wherein the method is performed by one or more computing devices ([col. 23, lines 30-40]).
As per claim 2, claim 1 is incorporated, Houlihan further discloses:
further comprising returning, in response to the query, information of stored data items pointed to by the first pointers ([col. 3, lines 7-10] When items are inserted into a table or a collection a pointer to that item is maintained for each attribute that is being indexed. The system then uses an index to query the table in order to produce a result set).
As per claim 5, claim 1 is incorporated, Houlihan further discloses:
wherein the second sorted structure comprises a hierarchical structure including nodes with the second pointers sorted based on the first attribute ([cols. 17-18, lines 59-13] At operation 1022, a secondary instance of the item is created according to a second key from the set of other keys. In some embodiments, the second key may be an item attribute to be used as an alternate partition key or alternate sort key of the secondary instance. The second key may be defined in a secondary facet schema specified in the insert request. In some embodiments, the creation may involve modifying the insert request to be sent to storage nodes or creating a data representation of the secondary instance to be inserted. In some embodiments, the creation involves copying attribute values of specified attributes in the item, according to the secondary facet schema, into one or more overloaded key fields in the secondary instance. At operation 1024, the secondary instance is stored in the table according to the second key. In some embodiments, the request router node may send the secondary instance to a partition group of the table to be stored. In some embodiments, the secondary instance is assigned to a partition group of the table according to the value of its partition key. In some embodiments, the secondary instance is stored in the partition in a sorted order according to the value of its sort key).
Regarding claim 11, Houlihan discloses:
One or more non-transitory storage media storing one or more sequences of instructions which, when executed by one or more computing devices, cause: receiving a query for stored data items that have a plurality of attributes that include a first attribute and a second attribute that has a hierarchical relationship with the first attribute ([col. 9, lines 41-45] the facet schemas may also define a list of projected attributes, such as projected attributes 184 and 194. In some embodiments, the projected attributes may be a subset of the attributes contained in the primary item instance 170 [col. 17, lines 8-21] The process of FIG. 10A illustrates an insert operation where the insert request specifies alternate keys for an item. The process begins at operation 1010, where a request is received from a client to insert an item into a table. The request may specify a first key for the item and a set of other keys for the item. In some embodiments, the first key may be an attribute of the item to be used as a partition key or sort key for a primary instance of the item. In some embodiments, the set of second keys may be alternative partition keys attributes or sort key attributes to be used for secondary instances of the item. In some embodiments, the insert request may specify a set of facet schemas, including a primary facet schema and a secondary facet schema, as shown in FIG. 2B);
performing a first sort of the stored data items based on a first set of ordering keys, the first set of ordering keys including the first attribute and the second attribute; performing a second sort of the stored data items based on a second set of one or more ordering keys, the second set being a proper subset of the first set and including the second attribute as an ordering key; generating a first sorted structure of the second sort of the stored data items; inserting first pointers into the first sorted structure,, where the first pointers point to the stored data items; generating a second sorted structure of the second sort of the stored data items; and inserting second pointers into the second sorted structure, where the second pointers point to the stored data items ([col. 3, lines 7-9] When items are inserted into a table or a collection a pointer to that item is maintained for each attribute that is being indexed [col. 17, lines 24-44] At operation 1012, the primary instance of the item is created according to the first key. In some embodiments, the creation may involve modifying the insert request to be sent to storage nodes. In some embodiments, the creation may create a data representation of the primary instance to be inserted. In some embodiments, the creation involves copying attribute values of specified attributes in the item, according to the primary facet schema, into one or more overloaded key fields in the primary instance. In some embodiments, the primary instance has an overloaded partition key field and an overloaded sort key field. At operation 1014, the primary instance is stored in the table according to the first key. In some embodiments, a request router node may send the primary instance to a partition group of the table to be stored. In some embodiments, the table is divided into a number of partitions, each managed by a group of storage nodes. In some embodiments, the primary instance is assigned to a partition group according to the value of its partition key. In some embodiments, the primary instance is stored in the partition in a sorted order according to the value of its sort key [cols. 17-18, lines 59-13] At operation 1022, a secondary instance of the item is created according to a second key from the set of other keys. In some embodiments, the second key may be an item attribute to be used as an alternate partition key or alternate sort key of the secondary instance. The second key may be defined in a secondary facet schema specified in the insert request. In some embodiments, the creation may involve modifying the insert request to be sent to storage nodes or creating a data representation of the secondary instance to be inserted. In some embodiments, the creation involves copying attribute values of specified attributes in the item, according to the secondary facet schema, into one or more overloaded key fields in the secondary instance. At operation 1024, the secondary instance is stored in the table according to the second key. In some embodiments, the request router node may send the secondary instance to a partition group of the table to be stored. In some embodiments, the secondary instance is assigned to a partition group of the table according to the value of its partition key. In some embodiments, the secondary instance is stored in the partition in a sorted order according to the value of its sort key).
Claims 12, 15 recite similar claim limitations as the method of claims 2, 5, except that they set forth the claimed invention as one or more non-transitory storage media and, as such, they are rejected for the same reasons as applied hereinabove.
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 3-4, 13-14 are rejected under 35 U.S.C. 103 as being unpatentable over Houlihan (US 11,461,302) in view of Armangau (US 8,412,688).
As per claim 3, claim 1 is incorporated, Houlihan fails to disclose “wherein the first sorted structure comprises a hierarchical structure including nodes with the first pointers sorted based on the second attribute, where each node includes at least one pointer to a stored data item”
However, Armangau teaches the above limitation ([cols. 18-19, lines 62-2] organizing each extent index 371, 372 as a list of pointers sorted by the starting offset associated with each pointer. A preferred organization is a B-tree, in which the sorted list of pointers is maintained as a hierarchy of nodes. Each parent node in the hierarchy has a sorted list of pointers to child nodes, and each node encompasses an offset range in the file).
Therefore, it would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to incorporate the teaching of Armangau into the teaching of Houlihan because the references similarly disclose data processing and/or indexing. Consequently, one of ordinary skill in the art would be motivated to further modify the system as in Houlihan to further include the organizing of the indexes as a list of pointers as in Armangau in order to allow for more efficient access to the referenced data.
As per claim 4, claim 3 is incorporated, Armangau further discloses:
wherein each node of the first sorted structure corresponds to a first attribute value and contains at least one pointer to a unique data item including the first attribute, where the unique data item is unique compared to other data items pointed to by other nodes; and wherein at least one node of the first sorted structure contains a plurality of pointers, each of the plurality of pointers pointing to a respective data item, where each data item pointed to by a pointer of the at least one node is unique compared to other data items pointed to by a pointer of the at least one node ([cols. 18-19, lines 62-2] organizing each extent index 371, 372 as a list of pointers sorted by the starting offset associated with each pointer. A preferred organization is a B-tree, in which the sorted list of pointers is maintained as a hierarchy of nodes. Each parent node in the hierarchy has a sorted list of pointers to child nodes, and each node encompasses an offset range in the file).
Claims 13-14 recite similar claim limitations as the method of claims 3-4, except that they set forth the claimed invention as one or more non-transitory storage media and, as such, they are rejected for the same reasons as applied hereinabove.
Claims 6-7, 16-17 are rejected under 35 U.S.C. 103 as being unpatentable over Houlihan (US 11,461,302) in view of Kothuri (US 6,470,344).
As per claim 6, claim 1 is incorporated, Houlihan fails to disclose “further comprising: comparing a particular first attribute of a particular stored data item to first attributes of stored data items pointed to by the second sorted structure; determining that the particular first attribute matches a first attribute of a stored data item pointed to by the second sorted structure; and determining, in response to determining that the particular first attribute matches the first attribute of the stored data item pointed to by the second sorted structure, whether to insert a pointer to the particular stored data item into the first sorted structure”
However, Kothuri teaches the above limitation ([col. 17, lines 55-67] [Step 2—Insert data item in leaf node and update nodes on insertion-path]
2.1 Initialize insertion-entry to the new data item
2.2 Initialize modified-entry to nil (i.e., empty)
2.3 While insertion-path is not empty, do:
2.3.1 Pop the top node in insertion-path, call it node1
2.3.2 Set old-MBA to the MBA of nodei
2.3.3 If modified-entry is not empty, then:
2.3.3.1 Identify the entry in nodei whose child reference (e.g., pointer, Row_id, Node_id) matches that of modified-entry
2.3.3.2 Replace the MBA of that entry in nodei with the MBA of modified-entry).
Therefore, it would have been obvious to one of ordinary skill in the art prior to the effective filing date of the claimed invention to incorporate the teaching of Kothuri into the teaching of Houlihan because the references similarly disclose data processing and/or indexing. Consequently, one of ordinary skill in the art would be motivated to further modify the system as in Houlihan to further include the hierarchical indexing methods and buffering as in Kothuri in order to greatly improve the performance of an index operation (Kothuri, [col. 23, lines 57-59]).
As per claim 7, claim 6 is incorporated, Kothuri further discloses:
wherein determining whether to insert the pointer to the particular stored data item into the first sorted structure comprises: determining that the pointer to the particular stored data item replaces a pointer to another stored data item in the first sorted structure; and in response to determining that the pointer to the particular stored data item replaces the pointer to the another stored data item in the first sorted structure: removing the pointer to the another stored data item from the first sorted structure and from the second sorted structure; and inserting the pointer to the particular stored data item into the first sorted structure and into the second sorted structure ([col. 17, lines 55-67] [Step 2—Insert data item in leaf node and update nodes on insertion-path]
2.1 Initialize insertion-entry to the new data item
2.2 Initialize modified-entry to nil (i.e., empty)
2.3 While insertion-path is not empty, do:
2.3.1 Pop the top node in insertion-path, call it node1
2.3.2 Set old-MBA to the MBA of nodei
2.3.3 If modified-entry is not empty, then:
2.3.3.1 Identify the entry in nodei whose child reference (e.g., pointer, Row_id, Node_id) matches that of modified-entry
2.3.3.2 Replace the MBA of that entry in nodei with the MBA of modified-entry).
Claims 16-17 recite similar claim limitations as the method of claims 6-7, except that they set forth the claimed invention as one or more non-transitory storage media and, as such, they are rejected for the same reasons as applied hereinabove.
Allowable Subject Matter
Claims 8-10, 18-20 are objected to as being dependent upon a rejected base claim, but would be allowable if rewritten in independent form including all of the limitations of the base claim and any intervening claims.
Conclusion
Any inquiry concerning this communication or earlier communications from the examiner should be directed to WILLIAM P BARTLETT whose telephone number is (469)295-9085. The examiner can normally be reached on M-Th 11:30-8:30, F 11-3.
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, Sherief Badawi can be reached on 571-272-9782. 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.
/WILLIAM P BARTLETT/
Primary Examiner, Art Unit 2169
Prosecution Insights