Ex Parte Cha et alDownload PDFPatent Trial and Appeal BoardMay 24, 201611934986 (P.T.A.B. May. 24, 2016) Copy Citation UNITED STA TES p A TENT AND TRADEMARK OFFICE APPLICATION NO. FILING DATE FIRST NAMED INVENTOR 111934,986 11105/2007 50400 7590 05/27/2016 SCHWEGMAN LUNDBERG & WOESSNER/SAP P.O. BOX 2938 MINNEAPOLIS, MN 55402 Sang Cha 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 ATTORNEY DOCKET NO. CONFIRMATION NO. 2058.134US2 6985 EXAMINER ADAMS, CHARLES D ART UNIT PAPER NUMBER 2164 NOTIFICATION DATE DELIVERY MODE 05/27/2016 ELECTRONIC 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. Notice of the Office communication was sent electronically on above-indicated "Notification Date" to the following e-mail address( es): uspto@slwip.com SLW@blackhillsip.com PTOL-90A (Rev. 04/07) UNITED STATES PATENT AND TRADEMARK OFFICE BEFORE THE PATENT TRIAL AND APPEAL BOARD Ex parte SANG CHA, SANGYONG HWANG, KIHONG KIM, KEUNJOO KWON, and KEUNJOO KWON 1 Appeal2014-001238 Application 11/934,986 Technology Center 2100 Before MAHSHID D. SAADAT, KRISTEN L. DROESCH, and KAMRAN JIVANI, Administrative Patent Judges. DROESCH, Administrative Patent Judge. DECISION ON APPEAL STATEMENT OF THE CASE Appellants seek review under 35 U.S.C. § 134(a) of the Examiner's Final Rejection of claims 1-20, 26-29, and 31-39.2 We have jurisdiction under 35 U.S.C. § 6(b). We AFFIRM-IN-PART. 1 Appellants indicate the real party-in-interest is SAP AG. App. Br. 2. 2 Claim 30 was objected to as dependent on a rejected claim, but indicated as being allowable if rewritten in independent form. Final Act. 2. Appeal2014-001238 Application 11/934,986 BACKGROUND The disclosed invention relates to an optimistic latch-free index traversal (OLFIT) concurrency control scheme for an index structure for managing a database system. Spec. Abs. Representative claim 1, reproduced from the Claim Appendix of the Appeal Brief, reads as follows: 1. A device for searching a database, the device comprising: a memory configured to store an index tree that has one or more nodes including a root node, each node associated with a latch governing concurrent access to the node and each node having contents including one or more keys including a high key, the high key denoting the upper bound of the one or more keys, a version number indicating a sequence of updates of the node contents, a link pointer pointing to a right sibling of the node at the same level and one or more pointers pointing to data items in the database in the case of a leaf node and to child nodes in the case of a non-leaf node; and a concurrency controller operatively coupled to the memory, the concurrency controller configured to: lock the latch of a first node that is traversed; update the contents of the first node after the latch of the first node is locked, the updating of the contents including updating at least one of the one or more keys, the link pointer or the one or more pointers; increment the version number included in the first node after the updating of the at least one of the one or more keys, the link pointer or the one or more pointers: and release he latch of the first node after the version number is incremented. REJECTIONS Claim 37 stands rejected under 35 U.S.C. § 112, first paragraph as failing to comply with the written description requirement. Claims 1, 4, 7-9, 11, 12, 14--18, 20, 26, 34, and 35 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Philip L. Lehman & S. Bing 2 Appeal2014-001238 Application 11/934,986 Yao, Hffzcient J,ocking for Concurrent Operations on R-Trees, 6 ACM TRANSACTIONS ON DATABASE SYSTEMS 650 (1981) ("Lehman") and Baird et al. (U.S. 5,410,697, iss. Apr. 25, 1995) ("Baird"). Claims 2, 31-33, 37, and 38 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Lehman, Baird, and Ishak et al. (US 5,475,837, iss. Dec. 12, 1995) ("Ishak"). Claims 3 and 36 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Lehman, Baird, Bridge, Jr. et al. (US 6,272,503 B 1, iss. Aug. 7, 2001) ("Bridge"), and Ishak. Claims 5 and 6 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Lehman, Baird, and Dijkstra et al. (US 6,411,957 B 1, iss. June 25, 2002) ("Dijkstra"). Claim 10 stands rejected under 35 U.S.C. § 103(a) as unpatentable over Lehman, Baird, and Davis et al. (US 7,093,109 Bl, iss. Aug. 15, 2006) ("Davis"). Claims 13 and 19 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Lehman, Baird, and Kothuri et al. (US 6,470,344 Bl, iss. Oct. 22, 2002) ("Kothuri"). Claim 27 stands rejected under 35 U.S.C. § 103(a) as unpatentable over Lehman, Baird, and Bacon et al. (US 6,772,153 Bl, iss. Aug. 3, 2004) ("Bacon I"). Claims 28 and 29 stand rejected under 35 U.S.C. § 103(a) as unpatentable over Lehman, Baird, Bacon I and Bacon (US 6,247,025 Bl iss. Jun. 12, 2001) ("Bacon II"). 3 Appeal2014-001238 Application 11/934,986 ANALYSTS We have reviewed the Examiner's rejection in light of Appellants' arguments in the Appeal Brief presented in response to the Final Office Action, and in light of the Reply Brief presented in response to the Examiner's Answer. We agree with Appellants that the Examiner erred in determining claims 1-20, 26-29, and 31-39 are unpatentable based on the applied prior art. We highlight and address specific findings and arguments for emphasis below. § 103 Rejections Appellants argue that modifying the teachings of Lehman by the teachings of Baird would render Lehman unsatisfactory for its intended purpose. See App. Br. 14--15. Appellants contend combining Baird's teaching to block read access to a page to update serial IDs would render Lehman unsuitable for its intended purpose of making sure that locks do not block read access. Id. at 15 More specifically, Appellants argue Lehman's system "is designed to ensure, and depends on, continuous read access to the data." App. Br. 14; Reply Br. 5. In support of its arguments, Appellants contend Lehman teaches a locking scheme that is simpler because no read-locks are used and only a small constant number of nodes are locked by any update process at any given time. Id. (citing Lehman, 650-651 ); see also Lehman 668---669. Appellants further assert Lehman teaches that no search through a tree is ever prevented from reading any node because locks only prevent multiple update access; locks do not prevent other processes from reading the locked page. Id. (citing Lehman 651 ). Appellants further contend Lehman distinguishes its approach to prior approaches that did block read access. Id. 4 Appeal2014-001238 Application 11/934,986 (citing Lehman 651 for a prior approach by Bayer and Schkolnick); see Lehman 656. Appellants argue Baird teaches that to update a serial ID of a page, read access to a page must be blocked and any copies of the page must be removed and re-read after the update is complete. Appeal Br. 15; Reply Br. 6. In support of its arguments, Appellants contend Baird teaches that when a process updates the page, the process presents a changed page N to a local cache manager (LCM) along with a serial ID 'a3 'as originally assigned. App. Br. 14--15 (citing Baird 7:27-29). Appellants further explain Baird teaches the serial ID is then compared to the current serial ID of page N and, if they match, an exclusive lock is acquired. Id. at 15. Appellants explain Baird teaches that at this point, any copies of page N are purged from caches and any share locks are released. Id. (citing Baird 7:30-45). Appellants contend that because an exclusive lock is acquired, pages are purged and share locks of the page are released, no other process can read the page until the update has occurred and a new share lock is reacquired. Id. (citing Baird 4:19-23); see Baird 7:56-57. Appellants further assert Baird teaches the share/exclusive lock granting order is the only granting order which ensures a comparison match between the version number obtained by a processor seeking to write a page update and the version number obtained by the LCM. App. Br. 15 (citing Baird 4:45-50). Appellants contend no other combination is possible in Baird, and both share locks and exclusive locks must be used. App. Br. 15; Reply Br. 6. The Examiner disagrees and asserts that Baird's locks do not block read access. Ans. 15 (citing Baird 2:40-41). The Examiner contends Baird's update lock merely forces a client on another processor currently reading a page to refresh that page to represent the most updated subject 5 Appeal2014-001238 Application 11/934,986 matter. Id. (citing Baird 7 :40-45). The Examiner further asserts "that users on the same processor may continue reading the out-of-date page (it will not be purged), with the provision that any updates the user attempts to perform on the stale page will be blocked. Id. (citing Baird 7:51-62). The Examiner contends nothing in Baird states that an update to a tree prevents a user from reading a node. Id. We agree with Appellants that an intended purpose of Lehman is to ensure continuous read access to the data because Lehman teaches "no search through the tree is ever prevented from reading any node (locks only prevent multiple update access)." See Lehman 651. We further agree Baird teaches that to update a serial ID of a page, read access to a page must be blocked and any copies of the page must be removed and re-read after the update is complete. See App. Br. 14--15. We observe that Baird teaches that during the update process, local cache copies of a page are removed and the share locks are relinquished, followed by the grant of an exclusive lock Baird 4:29--41, 7:26-50. Baird also explains a share lock on pages in memory or storage are associated with read and copy operations, and exclusive locks are associated with write/update and move operations. Baird 2:37--41. In other words, when share locks are relinquished as described in Baird, the pages can no longer be read-in effect the ability to read the pages is blocked. Therefore, we agree with Appellants that combining Baird's teachings of a read lock (i.e., relinquishing a share lock and applying an exclusive lock) during the process of updating a page serial ID with Lehman's system would render Lehman unsuitable for its intended purpose of ensuring continuous read access or making sure that locks do not block read access. 6 Appeal2014-001238 Application 11/934,986 Accordingly, we are constrained to reverse the rejection of independent claims 1, 15, 20, and 35, and dependent claims 4, 7-9, 11-12, 14, 16-18, 26, and 34 over Lehman and Baird. As applied by the Examiner, the additional cited prior art does not remedy the deficiencies of the combination of Baird and Lehman. See Final Act. 11-20. Therefore, for the same reasons as claims claims 1, 4, 7-9, 11-12, 14--18, 20, 26, 34, and 35, we are constrained to reverse the rejections of claims 2, 3, 5, 6, 10, 13, 19, 30-33, and 36-39 over Lehman, Baird, and the additional cited prior art references. § 112, First Paragraph Rejection The Examiner rejected claim 37 under 35 U.S.C. § 112, first paragraph as failing to comply with the written description requirement. Appellants assert the rejection of claim 37 is not a subject of this appeal. App. Br. 9. Our rules state that an appeal is presumed to be taken from the rejection of all of the claims under rejection unless cancelled by an entered amendment. See 37 C.F.R. 41.3 l(c). Appellants do not present arguments addressing the rejection of claim 37 under 35 U.S.C. § 112, first paragraph. Accordingly, we sustain proforma the rejection of claim 37 under 35 U.S.C. § 112, first paragraph. DECISION We AFFIRM the rejection of claim 37 under 35 U.S.C. § 112, first paragraph. We REVERSE the rejections of claims 1-20, 26-29, and 31-39 under 35 U.S.C. § 103(a). No time period for taking any subsequent action in connection with this appeal may be extended under 37 C.F.R. § 1.136(a)(l )(iv). 7 Appeal2014-001238 Application 11/934,986 AFFIRMED-TN-PART 8 Copy with citationCopy as parenthetical citation