T 0279/09 (Layered index/ORI) of 16.3.2015

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the Examining Division to refuse the European patent application no. 99901096.0.

II. According to the contested decision, the appellant's only remaining request admitted into the proceedings, i.e. the third auxiliary request dated 29 May 2008, did not fulfill the requirements of Article 84 EPC.

III. With the statement of grounds of appeal, dated 24 December 2008, the appellant filed a new set of claims 1 to 29 and requested that the decision under appeal be set aside and a patent be granted on the basis of the newly submitted claims. Furthermore, the appellant requested remittal to the department of first instance, should the Board not be inclined to grant a patent.

IV. Claim 1 filed with the statement of grounds of appeal reads as follows:

"A method for improving access to data records associated with a basic partitioned index I0 by constructing a balanced layered index I0, ..., Ih arranged in blocks over said data records, each one of said blocks having a memory size suitable for reading by a single I/O operation and each one of said blocks being represented by a representative key, said basic partitioned index enabling accessing and updating the data records by key or keys and being susceptible to be unbalanced, said method being for use in a database file management system for accessing said records and being executed on a data processing system, the method comprising the steps of:

a) providing said basic partitioned index I0 arranged in blocks and being stored in a storage medium;

b) dynamically constructing a representative index comprising one or more layers I1, ..., Ih over said partitioned index I0, wherein each layer is partitioned into blocks and wherein each layer Ig (0<g<=h) is an index over the representative keys of the blocks of layer Ig-1, the construction comprising the steps of:

(i) if a block B in a layer Ig-1 (1<=g<=h) overflows then splitting said block B into two or more blocks such that the block being split in layer Ig-1 is replaced by the two or more new blocks and replacing the representative key of block B in Ig by the representative key of each of the new blocks,

(ii) if a block B in layer Ih overflows then splitting said block B into two or more blocks such that the block being split in layer Ih is replaced by the two or more new blocks, creating an additional layer Ih+1, adding the additional layer Ih+1 to said layered index and updating said layer Ih+1 such that each block B in layer Ih is represented in layer Ih+1 by the representative key of block B. [sic]

thereby creating a balanced layered index I0, ..., Ih allowing search for any one of the said records by a key through said blocks in the layered data index."

V. With letter dated 11 December 2014, the appellant was summoned to oral proceedings before the Board.

VI. In a communication dated 21 January 2015 pursuant to Article 15(1) RPBA, the Board made some observations under Article 84 EPC and indicated that it intended to remit the case to the department of first instance for further prosecution, if the outstanding clarity issues could be overcome.

VII. In reply to the Board's communication, the appellant submitted, with a letter dated 16 February 2015, two sets of claims as a new main request and an auxiliary request, thereby replacing the claims filed with the statement of grounds of appeal. Furthermore, the appellant indicated that it would be very much appreciated if the proceedings could be concluded in writing.

VIII. In a communication sent by fax on 3 March 2015, the Board noted that the new requests, which appeared to be substantially different from the requests filed with the statement of grounds of appeal, gave rise to new clarity issues. Furthermore, the Board expressed the view that a favorable conclusion of the proceedings in writing was unlikely, and that the outstanding objections could be best overcome if the matter were to be discussed at oral proceedings. Hence, the appellant was strongly recommended to attend the oral proceedings scheduled for 16 March 2015.

IX. By fax received at 7:38 hours on 16 March 2015 the representative of the appellant informed the Board that the appellant had decided not to attend the oral proceedings.

X. Oral proceedings were held as scheduled on 16 March 2015 in the absence of the appellant. At the end of these proceedings, the Chairman pronounced the Board's decision.

XI. The appellant requested (cf. letter dated 16 February 2015) that the decision under appeal be set aside and the case be remitted to the department of first instance for further prosecution on the basis of the claims of the main request or, if this was not possible, on the basis of the claims of the auxiliary request, both requests having been filed with letter dated 16 February 2015.

XII. Claim 1 of the main request reads as follows:

"A method for constructing a layered index arranged in blocks, said method being used by a database file management system for accessing data records and executed on data processing system, said method comprising the steps of:

providing a basic partitioned index arranged in blocks and being stored in a storage medium, the basic partitioned index enabling accessing or updating data records associated with said basic partitioned index by key or keys and being susceptible to an unbalanced structure of blocks;

constructing said layered index by constructing a representative index over the representative keys of said basic partitioned index, a representative key enabling identification of a block associated with a particular record; said layered index enabling accessing or updating the data records by key or keys and constituting a balanced structure of blocks, wherein constructing a representative index includes:

deleting at least one short link among the short links of a node in block Bi-1 in a way that at least two tries exist in said block, said deteted [sic] node [sic] being referred to as split link and said said [sic] node being referred to as a split node;

moving each of the sub-trees to a separate block Bi;

if the block Bi does not exist, creating Bi and creating a copied node of the split node in block Bi;

if the block Bi exists and a copied node of the split node does not exist in block Bi, then creating a copied node of the split node in Bi and connecting to the trie of block Bi such that block Bi-1' is accessible in a search path that includes the root node in block Bi and the copied node and its labeled links according to the representative key of block Bi-1',

if the copied node has no direct link, adding a direct link from the copied node to the block Bi-1';

adding a far link from the copied node to the block Bi-1'; or, if the copied node has a short link to a child node in the direction of the far link, replacing the far link by a direct link from the child node to block Bi-1'."

It is evident from the context of the above claim that " ... said deteted node being referred to as split link ..." should read "... said deleted link being referred to as split link ...".

Claim 1 according to the auxiliary request differs from claim 1 of the main request only in that its second paragraph reads as follows:

"... providing a basic partitioned index arranged in blocks and being stored in a storage medium, a block being a storage unit accessible by a single I/O operation, the basic partitioned index being an [sic] trie and enabling accessing or updating data records associated with said basic partitioned index by key or keys and being susceptible to an unbalanced structure of blocks; ..."

XIII. In support of its requests, the appellant argued essentially as follows:

Claim 1 of the main request was a combination of claims 26 and 60 of the claims as originally filed, but claim 26 had been reworded as a regular process claim. Hence, claim 1 was directed to a method of constructing a layered index as recited in claim 26 as originally filed.

A clarification regarding the term "representative key" had been added to the claim in the sense that such key enabled identification of a block associated with a particular record. Support for the new wording could be found on page 14, lines 12 to 20 of the application as originally filed.

The features of claim 60 as originally filed related to the "split process" as mentioned on page 19, lines 7 to 23 of the application as originally filed. This process took place when constructing the "layered index" and included dividing a vertical index tree in blocks, creating a block with an index having nodes which reproduced some tree nodes, and linking each block of the initial partitioned index either by a direct link or a far link. This process was illustrated with reference to Figures 7 to 9 and page 51, lines 12 to 15 of the application as originally filed.

Thus, the wording of claim 1 comprised a clear definition of the representative key as well as the process steps that were necessary to create the layered index.

Claim 1 according to the auxiliary request was based on the combination of claims 1 and 2 of the main request and further comprised the clarification that the blocks were storage units accessible by a single I/O operation.

Reasons for the Decision

1. The appeal is admissible.

Admissibility of the appellant's requests

2. The main request and the auxiliary request were filed a month before the date scheduled for the oral proceedings in reply to clarity objections raised in the Board's communication dated 21 January 2015.

2.1 The Board accepts that the requests on file constitute a bona fide attempt on the part of the appellant to clarify some important aspects of the present invention in order to overcome the Board's objections.

2.2 In these circumstances, the Board finds it appropriate to admit the appellant's requests into the appeal proceedings despite their late filing.

Main request

3. As indicated by the appellant, claim 1 of the main request is based on a combination of claims 26 and 60 as originally filed, whereby independent claim 26 is directed to a "method for constructing a layered index arranged in blocks", and claim 60, dependent on claim 26, specifies the step of "constructing a representative index over the representative keys of" a "basic partitioned index".

This process is illustrated in Figures 7 to 9 of the application as originally filed.

4. The first paragraph of claim 26 defines the actual context for the implementation of the method as:

"a database file management system for accessing data records and being executed on data processing system".

In the same paragraph the arrangement of the data records is specified as follows:

- the data records are associated with a basic partitioned index arranged in blocks and

- being stored in a storage medium.

As to the "basic partitioned index", claim 26 recites the following:

- the basic partitioned index enables accessing or updating the data records by key or keys, and

- it is susceptible to an unbalanced structure of blocks.

4.1 According to claim 26, the "layered index" is constructed by:

(x) providing said basic partitioned index;

(y) constructing a "representative index over the representative keys" of said basic partitioned index.

Like the basic partitioned index, the "layered index" enables accessing or updating the data records by key or keys. Moreover, it constitutes a balanced structure of blocks (see last clause of claim 26).

4.2 In other words, claim 26 of the original application is directed to a method for constructing a "layered index" on the basis of a "representative index" and a "basic partitioned index". However, this claim does not give any detail concerning the actual steps for arriving at a "layered index" with a balanced structure of blocks.

4.3 The step of constructing a "representative index" according to claim 1 is essentially taken from claim 60 as originally filed and comprises the following features:

a) deleting at least one short link among the short links of a node in block Bi-1 in a way that at least two tries exist in said block,

i) said deleted link being referred to as split link and said node being referred to as a split node;

b) moving each of the sub-trees to a separate block Bi;

c) if the block Bi does not exist,

i) creating Bi and

ii) creating a copied node of the split node in block Bi;

d) if the block Bi exists and a copied node of the split node does not exist in block Bi, then

i) creating a copied node of the split node in Bi and

ii) connecting to the trie of block Bi such that Bi-1' is accessible in a search path that includes the root node in block Bi and the copied node and its labeled links according to the representative key of block B1-i',

e) if the copied node has no direct link, adding a direct link from the copied node to the block Bi-1';

f) adding a far link from the copied node to the block Bi-1'; or,

g) if the copied node has a short link to a child node in the direction of the far link, replacing the far link by a direct link from the child node to the block Bi-1'.

5. An application of the method of the invention is shown in Figures 7A to 7C of the application. A "basic partitioned index" in the form of a "tree" or "trie" is arranged in a block 140 (Figure 7A). This index is not "balanced", as the paths from the root node A to the various leaf nodes vary in length.

5.1 If block 140 overflows in terms of memory space, link 149 is split and two blocks 146 and 148 are formed. As long as the two blocks are connected by the link 150, all leaf nodes H, J, K and L of block 148 can be reached from the root node A. According to the invention, a "father block" 144 is created with a "duplicated node A'" of node A. A link 145 connects A' with block 146 and link 147 connects A' with block 148, whereby link 147 has the same value as link 149 and link 150 (see Figure 7B). As pointed out in the description (page 52, second paragraph), blocks 144, 146 and 148 constitute a "layered index" and the corresponding layers I1 and I0 are so linked that all data records in blocks 146 and 148 can be accessed from node A' in block 144. In the particular case of Figure 7B there appears to be no advantage in having a two-layered index since the data records of block 148 are always accessed through another block, i.e. either through block 144 in case of the "horizontal" tree formed by blocks 144, 146 and 148, or through block 146 in case of the "vertical" tree formed by blocks 146 and 148.

5.2 Figure 7C shows the result of splitting link 152 and dividing the trie in block 148 into two blocks 148A and 148B. The node C from which the split link originates is duplicated in block 140, marked C' and connected to node A' via a link 158 which has the same value as link 150. A direct link 154 links blocks 140 and 148A, whereas a far link 155 links C' with block 148B and has the same value as link 152. As it appears from Figure 7C, through the addition of an index layer the data records of block 148B can be accessed via block 140 instead of accessing them via blocks 141 and 148A. In fact, all blocks of layer I0 (i.e. 141, 148A and 148B) can be accessed directly from block 140 of layer I1, so that the "layered index" constructed over the original "basic partitioned index" (see Figure 7A) has a balanced structure.

6. As pointed out above, the first part of claim 1 refers in general to a "basic partitioned index" and to a "layered index" constructed over the basic partitioned index. In the second part of the claim, however, it is recited that a short link in a block is deleted in such a way that "at least two tries exist in said block". As explained in the description, a "trie" is a tree with a particular index structure. The fact that splitting a link in a block results in two tries in the block appears to imply that the basic partitioned index is in fact a trie comprising nodes connected by short links.

6.1 According to feature b) "each of the sub-trees" is moved to a separate block Bi. If it can be understood that the term "sub-trees" is intended to identify the tries that exist in a block Bi-1 after deleting a short link, the reference to a block Bi is not consistent with the disclosure and with the original application.

Apart from the fact that in the description of Figures 7 to 9 a generic layer of the layered index is identified as Ij (see page 53, last line), constructing a representative index according to the present invention does not involve the step of moving each of the sub-trees resulting from splitting a link to a separate block of a higher level, as the indexing used in the claim suggests. On the contrary, only one of the two sub-trees is moved into a block in the same layer of the layered index.

6.2 Hence, the step of moving each of the sub-tries to a separate block Bi and creating a copied node of the split node in block Bi is not consistent with the original disclosure. As specified in the paragraph bridging pages 18 and 19 of the description, the "access path to block Bi-1 of [the index layer] Ii-1 consists of block Bi of layer Ii". If block Bi-1 overflows it is split into blocks Bi-1 and Bi-1'. On page 19 it is explained in detail how the split process is carried out and how new blocks and links are created.

6.3 Features c) ii), e), f) and g) make also confusing use of the index B1-i' and of the terminology adopted to define links between a copied node and a block. In fact, it appears from the wording of the claim that the same block B1-i' is connected to a copied node by a direct link and by a far link.

6.4 In summary, claim 1 comprises several features which are not consistent with the disclosure of the invention and which are not the result of evident typographical errors which could be easily corrected by the reader (Article 84 EPC).

7. Besides the above objections relating to some of the claimed features, claim 1 does not seem to specify the actual construction of a balanced layered index starting from a basic partitioned index, but it appears to recite only steps which could at the most maintain a layered index with a balanced structure of blocks, as links in a block are split and new blocks are formed in order to accommodate new records.

7.1 In fact, whereas claim 1 of the main request submitted with the statement of grounds of appeal specified in feature (y) the step of dynamically constructing a representative index comprising one or more layers I1, ..., Ih over a partitioned index I0, features a) to g) of claim 1 of the main request on file can be understood as relating to the process of expanding a balanced layered index as new data records are added.

7.2 In other words, it cannot be understood from the wording of claim 1 how the problem of the invention is actually solved, namely how, starting from a generic (unbalanced) basic partitioned index, it is possible to arrive at a layered index constituting a balanced structure of blocks (Article 84 EPC).

7.3 In the Board's view, the above objections are of such a nature that they could not be overcome by straightforward editorial amendments of the claim wording.

Auxiliary request

8. Claim 1 according to the auxiliary request differs from the main request only in that it specifies the following:

- a block is a storage unit accessible by a single I/O operation, and

- the basic partitioned index is a trie.

9. It is evident that the above amendments do not address the clarity objections raised by the Board with respect to the main request.

10. In summary, none of the appellant's requests complies with Article 84 EPC. As clarity objections had caused the refusal of the application and were thoroughly focused upon in the appeal proceedings, the Board considers that the appellant's request for remittal of the case to the department of first instance for further prosecution cannot be acceded to.

11. Hence, the appeal has to be dismissed.

Order

For these reasons it is decided that:

The appeal is dismissed.