|European Case Law Identifier:||ECLI:EP:BA:2009:T176006.20090617|
|Date of decision:||17 June 2009|
|Case number:||T 1760/06|
|IPC class:||G06F 17/30|
|Language of proceedings:||EN|
|Download and more information:||
|Title of application:||Method and apparatus for fast and comprehensive DBMS analysis|
|Applicant name:||Computer Associates Think, Inc.|
|Relevant legal provisions:||
|Keywords:||Inventive step - main request and first and second auxiliary requests (no)
Remittal - third auxiliary request
Reimbursement of appeal fee (no)
Summary of Facts and Submissions
I. This appeal is against the decision of the examining division to refuse European patent application No. 99946689.9.
II. The following documents will be referred to:
D1: "Table reorganization identification", IBM Technical Disclosure Bulletin, XXXIV(1), 1991, 163-5
D2: US-A-5 222 235
E1: L. Leverenz et al, "Oracle8**(TM) Server Concepts", Manual, Oracle Corporation 1997, pp. 1-15, 1-19, 1-20.
III. According to the decision appealed, the subject-matter of claim 1 of the then main request did not involve an inventive step. The two auxiliary requests were not admitted under Rule 86(3) EPC 1973.
IV. With the statement setting out the grounds of appeal dated 30 October 2006, the appellant requested that the decision under appeal be set aside. Claims according to a new main request and three auxiliary requests were submitted. Refund of the appeal fee was also requested because of procedural violations by the examining division, in particular by inappropriately exercising its discretion under Rule 86(3) EPC 1973 when not admitting the then second auxiliary request into the proceedings (now filed as third auxiliary request).
V. In a communication annexed to a summons to oral proceedings, the Board indicated that the subject-matter of claim 1 according to the main and first two auxiliary requests appeared to be obvious having regard to a combination of D1 and D2. As to the third auxiliary request, its admissibility would be discussed at the hearing. Finally, reimbursement of the appeal fee did not seem equitable in the present case.
VI. By letter dated 15 May 2009 the appellant filed claims according to an amended main request and an amended third auxiliary request.
VII. Oral proceedings were held on 17 June 2009. The appellant, after having presented the new document E1, requested that the decision under appeal be set aside and a patent be granted on the basis of the main request filed by letter dated 15 May 2009, or auxiliary request 1 or 2 filed with the statement setting out the grounds of appeal dated 30 October 2006, or auxiliary request 3 filed by letter dated 15 May 2009. Additionally, reimbursement of the appeal fee was requested.
VIII. Claim 1 according to the main request reads:
"A method of analysis of a database, comprising:
identifying (100) a table in said database;
reading each of blocks associated with said table using direct asynchronous I/O; and
performing said analysis based on information contained in said blocks; characterised in that
creating plural block lists (110), each list identifying a set of blocks associated with said table;
spawning (110) plural threads; and
performing the following for each respective thread,
assigning (115) one of said plural block lists to the respective thread,
reading (120) each block identified by the assigned block list using direct asynchronous I/O,
gathering (125) information for said analysis utilising data contained in each block read, and
summing and averaging the information gathered by each thread to perform said analysis".
IX. Claim 1 of auxiliary request 1 is identical with that of the main request except for its first part, which reads:
"A method of analysis of a database, comprising:
identifying (100) a table in said database;
creating an extent list for the table to determine how many blocks need to be processed;
creating plural block lists (110), each list identifying a set of blocks associated with said table; [etc.]".
X. Claim 1 of auxiliary request 2 is identical with that of auxiliary request 1 except that the third method step reads:
"creating plural block sublists (110), each sublist identifying a set of blocks associated with said table and each created using an equal number of blocks or proportionately as close to equal as possible".
XI. Claim 1 of auxiliary request 3, which is largely identical with the second auxiliary request before the examining division, reads:
"A computer-implemented method of determining a condition of a database for reorganizing a table thereof, wherein the database is formed of blocks and has a percentage free threshold for row migration within each block and a percentage used threshold to permit additional rows to be inserted in each block, the method comprising the steps of:
identifying a database table;
determining elements corresponding to the condition of the database table based on data contained in the database table; and
providing said elements to one of a display for viewing by a user, a storage location, and a mechanism for using said elements; characterized in that said elements include number of blocks exceeding the percentage used threshold and number of blocks less than the percentage free threshold,
for rebuilding the table with adjusted values for the percentage free threshold and/or percentage used threshold".
XII. At the end of the oral proceedings the Board announced its decision.
Reasons for the Decision
1. Interpretation of claim 1
The appellant has pointed out that the last method step of claim 1 is not performed for each thread, but takes place once all threads have finished processing (cf fig. 4). The Board will interpret the claim accordingly.
2. The prior art
2.1 D1, entitled "Table reorganization identification", concerns a program tool to be used with a database management system (DBMS) for identifying tables that have undergone extensive changes and therefore need to be reorganised. The program collects statistical data about a table to be analysed and calculates various indicators of its level of disorganisation. D1 notes that the time needed for the analysis will depend on the table size (p. 165, top).
2.2 D2 describes a method of reorganising tables (rather than analysing them). Its starting point is the DBMS DATABASE 2 (DB2). A tool called DB2 REORG is conventionally used to reorganise a table. This tool contains the routine UNLOAD which reads all the data from a file to be reorganised (see section 1.10 in col. 5). The tool is said to be inefficient (see section 2.3 in col. 7) and D2 proposes improvements, some of which will be discussed in detail further below (see points 4.2 and 4.4).
3. The technical problem and its solution
3.1 D1 discloses a method of analysis of a database. A table in the database is identified and its blocks are read out. Nothing is said about how the reading is performed. The skilled person was thus faced with the problem of finding a way of reading out the blocks.
In the Board's view it was clearly desirable that the reading should be fast since the analysis prevents normal use of the table. The appellant, however, has argued that D1 teaches away from considerations about the read-out speed since it explicitly mentions the table size, leading the skilled person to limit the size of tables. The Board is nevertheless of the opinion that it was a mere matter of common sense to realise that the time a task takes does not only depend on its size but also on the speed with which it is performed. Furthermore, the skilled person could be expected to pay particular attention to the I/O operations, which are known to be relatively slow.
3.2 The technical problem of finding a fast method of reading out data blocks is according to the invention solved by two different means, claimed in combination: "threading" and "direct asynchronous I/O". Whereas threading is a well-known technique, involving parallel processing, "direct asynchronous I/O" has not been shown to have a generally accepted meaning. It is defined in the description (p. 23, bottom) in the following way: "By using direct asynchronous I/O to read database files, Fast Analysis /ie the invention/ is able to directly access specific blocks of a file, thereby bypassing the overhead of typical DBMS routines (SQL shared memory techniques, and other parameters required to access the database tables, for example)". It can thus not be equated with conventional asynchronous (interrupt-driven) I/O, but additionally implies circumventing DBMS overhead.
4.1 Searching for a solution to the above read-out problem, the skilled person would in the Board's view find D2 which concerns the reorganisation of data tables. It is true that the appellant denies that he would have since D2 does not deal with table analysis and thus in the appellant's opinion belongs to a different technical area. The Board, however, noting that both D1 and D2 mention table reorganisation and that an analysis of a table would be pointless unless a reorganisation was contemplated, cannot accept this argument. Table analysis and reorganisation are closely related techniques, and one important feature they have in common is the reading of table data.
4.2 Already the abstract of D2 mentions that the reorganisation method proposed "explores parallel processing and asynchronous I/O to a great extent". In section 1.5 (col. 3) various multi-tasking and multi-processor techniques are mentioned, and it is pointed out that "programs running in multitasking and/or multiprocessor environments may be designed to communicate with each other. This enables processes that are not independent of each other to execute in parallel". The Board understands this passage as referring to multiple threads. The appellant disagrees, pointing out that the reference is not to "threads" but to "programs". However, even if the word "thread" is not expressly mentioned the Board believes that the skilled person could not help thinking of threads in the given context. It is generally known that threads are parallel processes particularly distinguished by their use of a single process address space, ie by their interdependence. In referring to mutually dependent parallel processes, D2 therefore in the Board's view led the skilled person to the idea of reading blocks using a threading technique.
4.3 The second key feature in claim 1 is the "direct asynchronous I/O". As already noted, this expression must be regarded as implying that the overhead of (some) DBMS routines is bypassed. This means operating outside the conventional DBMS. A crucial question is thus whether the skilled person would at all have considered such a step.
4.4 In the Board's view this question can be readily answered with "yes" since it is exactly what D2 recommends. D2 starts out from conventional DB2. The known read-out routine UNLOAD does not use parallelism (col. 5, l. 64,65) and therefore the DB2 components do not "perform at an optimum level. Partitions could actually be loaded in parallel" (col. 6, l.21-25). The invention in D2 employs "concurrent unloading of partitions" (col. 6, l. 53,54), involving "asynchronous I/O" (col. 7, l. 37). "The method provides for its own I/O, independent of DB2, thereby enhancing the I/O algorithm" (col. 7, l. 51,52). These quotations demonstrate that the skilled person was well aware of the limitations of conventional DBMSs and would recognise the advantages of developing alternative functions. For the sake of completeness it might be added that it is not an indication of non-obviousness that such a development might be both complex and expensive: merely making the proposal is neither.
4.5 The appellant has argued that the skilled person would not have realised that a conventional DBMS analysis command incurs overhead. This was the inventor's own non-obvious discovery.
The application gives some examples of such overhead, such as "SQL shared memory techniques" (cf the quotation at point 3.2 above). At the oral proceedings before the Board the appellant, referring to E1 (p. 1-15), explained that shared memory was usually regarded as necessary for optimal performance. In particular it was used for the cache. The Board, while accepting that shared memory may well have excellent properties in many respects, remains unconvinced that the skilled person would cling to this concept even when it could offer no advantages. If it was desirable to read data fast he would design a system that did just that. This meant in particular eliminating, as far as possible, any factors that could be seen to slow down the process. What the application simply refers to as "overhead" would be recognized as such by a skilled person who was well familiar with the prior art within his technical area. Whether or not he was prepared to eliminate a specific instance of overhead would depend on whether he actually needed the advantages it offered. With respect to the shared memory, for example, E1 mentions that it serves to "minimize disk I/O" (p. 1-15), something which is hardly of interest if the very aim is to perform I/O commands. Moreover, the application is wholly silent on the measures to be taken in order to bypass the overhead. The bypassing step must thus be assumed to have been straightforward, suggesting that the overhead was manifestly irrelevant for the I/O operation.
4.6 Finally, the appellant has argued that the last feature of claim 1 - "summing and averaging the information gathered by each thread to perform said analysis" - was a non-obvious selection since other alternatives could be envisaged, such as performing the arithmetics together with the I/O operations in each thread. But also this argument cannot be accepted by the Board. The I/O operations would obviously be performed thread-wise since this is where considerable time saving could be expected. But the same is not necessarily true for the arithmetic operations. Whether or not they would be suitable for parallel processing would depend on their nature. Since the skilled man was familiar with both elementary mathematics and threading, he would have been able to decide at what point to perform the summing and averaging of data mentioned in the claim. Simply trying out the limited number of options would also have been straightforward. That the claimed alternative should be surprisingly efficient has not been disclosed or argued, nor does it appear likely.
4.7 It follows that the subject-matter of claim 1 does not involve an inventive step (Article 56 EPC 1973).
Auxiliary request 1
5. According to auxiliary request 1 an extent list is created. This extent list "need only identify the location(s) of all space allocated for the identified table" (p. 25, l. 8-10). Since a table obviously cannot be read and analysed unless its location in the memory is known, this request must also be refused (Article 56 EPC 1973).
Auxiliary request 2
6. According to auxiliary request 2 the set of blocks assigned to each thread consists of an (approximately) equal number of blocks. Noting that the purpose of the threads is to achieve concurrent processing, the Board regards it as a first choice to distribute the tasks evenly between the threads. D2 seems to adhere to the same principle since "an optimal number of partitions to be assigned to each task" is calculated (col. 10, l. 19-21), suggesting a single number of partitions per task. Thus, this request must also be refused (Article 56 EPC 1973).
Auxiliary request 3
7. Auxiliary request 3 corresponds to auxiliary request 2 before the examining division which was not admitted into the procedure under Rule 86(3) EPC 1973. The examining division was of the opinion that the subject matter defined therein returned to matter largely discussed and objected to much earlier in the written procedure and referred to its first communication of 8 April 2004. In addition, in its immediate opinion the subject matter of claim 1 was not so as to support an assertion of an inventive step (decision under appeal, points 24.2 ff).
In its first communication the examining division had raised objections under Rule 29(2) and Article 54(1) and (2) EPC 1973 stating that the application contained eight independent claims which did not fall within one or more of the exceptional situations set out in paragraphs (a), (b) or (c) of Rule 29(2) EPC 1973 and moreover were all not novel. In reply the appellant filed amended claims thereby focusing on original claim 12 depending on original independent claim 10. After the examining division had taken a negative view on the preceding requests, the appellant filed the present auxiliary request which was mainly based on a version of original claim 1 limited to the number of blocks in relation to percentage used and percentage free thresholds, and which additionally contained the feature that these numbers were used for "rebuilding the table with adjusted values for the percentage free threshold and/or percentage use threshold". This covers another aspect of the invention which had never been examined by the examining division and which was not a subject of its first communication. It also does not seem that a proper inventive step assessment based on this additional feature was made, so that the reasons given by the examining division for not admitting this request were not correct.
Moreover, in the Board's view it seems legitimate to file such a request specifically since the elements "number of blocks exceeding the percentage used threshold" and "number of blocks less than the percentage free threshold" were subject of original claim 1. The reason why the appellant concentrated on the subject matter of original claim 12 in the first place was the objection under Rule 29(2) EPC 1973. It also does not seem that this request was filed too late since it was submitted one month prior to the oral proceedings, and was amended three days before the oral proceedings due to an Article 123(2) EPC objection raised by the examining division. The amendments made during the oral proceedings were of a purely formal nature. Thus, the examining division could have dealt with this request in the oral proceedings without delaying the procedure. Therefore, in this specific situation, the examining division should have allowed the request into the procedure.
Since, as set out above, auxiliary request 3 covers a different aspect of the invention which has not yet been examined by the examining division, the Board remits the case to the department of first instance for further prosecution (Article 111(1) EPC 1973).
Reimbursement of the appeal fee
8. The appellant requested reimbursement of the appeal fee because in its view the examining division had not used its discretion in an appropriate manner when not admitting the second auxiliary request. As set out above, the reasons given by the examining division for not admitting this request were not correct. Thus it started from wrong assumptions when using its discretion which resulted in the wrong application of the law but does not qualify as a substantial procedural violation (Rule 67 EPC 1973).
For these reasons it is decided that:
1. The decision under appeal is set aside.
2. The case is remitted to the department of first instance for further prosecution on the basis of claims 1-3 according to auxiliary request 3.
3. The request for reimbursement of the appeal fee is refused.