T 1944/08 (Organising data/BERNARD CONSULTING) of 20.2.2014

European Case Law Identifier: ECLI:EP:BA:2014:T194408.20140220
Date of decision: 20 February 2014
Case number: T 1944/08
Application number: 02712086.4
IPC class: G06F 17/30
Language of proceedings: EN
Distribution: D
Download and more information:
Decision text in EN (PDF, 327.766K)
Documentation of the appeal procedure can be found in the Register
Bibliographic information is available in: EN
Versions: Unpublished
Title of application: Organising data in a database
Applicant name: Bernard Consulting Limited
Opponent name: -
Board: 3.5.07
Headnote: -
Relevant legal provisions:
European Patent Convention Art 56
European Patent Convention Art 84
Keywords: Claims - clarity - main request (no) - second auxiliary request (no) - third auxiliary request (no)
Inventive step - first auxiliary request (no)
Catchwords:

-

Cited decisions:
-
Citing decisions:
-

Summary of Facts and Submissions

I. The applicant (appellant), which at the time was Coppereye Limited, filed an appeal against the decision of the Examining Division refusing European patent application No. 02712086.4. The notice of appeal was received on 10 July 2008, the appeal fee having been paid on 9 July 2008. The statement of the grounds of appeal was received on 11 September 2008.

II. With effect from 2 April 2012 the application was transferred to Bernard Consulting Limited, which thereby obtained the status of appellant.

III. In the contested decision, the Examining Division came to the conclusion that claim 1 of both the main request and the auxiliary request was unclear within the meaning of Article 84 EPC. In an obiter dictum, reasons were presented as to why the subject-matter of claim 1 of both requests lacked an inventive step over document

D5: Van den Bercken J., Seeger B., Widmayer P.: "A Generic Approach to Bulk Loading Multidimensional Index Structures", Proceedings of the 23rd International Conference on Very Large Data Bases: VLDB '97, August 25-29, 1997, Athens, Greece, pages 406-415, Morgan Kaufmann 1997, ISBN 1-55860-470-7.

IV. With the statement of the grounds of appeal, the appellant requested that the decision under appeal be set aside and that a patent be granted on the basis of the claims of the main request filed with its letter dated 14 April 2008, or alternatively on the basis of the claims of one of the three auxiliary requests filed with the statement of the grounds of appeal. The second auxiliary request corresponded to the auxiliary request before the Examining Division. Oral proceedings were requested in the event that the Board was unable to grant the patent as requested.

V. Oral proceedings were appointed by the Board. In a communication accompanying the summons to oral proceedings, the Board expressed the provisional opinion that none of the appellant's requests was allowable.

VI. With a letter dated 18 February 2014, received by fax on the same day, the appellant advised the Board that it would not be attending the oral proceedings. The letter did not address any of the objections raised in the communication accompanying the summons.

VII. The oral proceedings took place on 20 February 2014 in the absence of the appellant. At the end of the oral proceedings, the chairman announced the decision of the Board.

VIII. Claim 1 of the appellant's main request reads as follows:

"A method of organising storage of data in a database (2), in which conclusion sets (20, 24, 26, 28, 30; 40, 50, 60) for the database are arranged in a hierarchical structure with a plurality of levels of significance including a first level of significance (level 1) and a very least significant level of significance, the conclusion sets storing data which matches search criteria or pointers which point to the location of the data which matches the search criteria, and in which the conclusion sets are arranged such that items are inserted into a selected conclusion set at the first level of significance (level 1) until the number of items reaches a threshold value for the selected conclusion set, and then the contents of the selected conclusion set are migrated to subordinate conclusion sets, thereby emptying the selected conclusion set, and wherein following migration of the contents from the selected conclusion set, further insertions can be made into that conclusion set, characterised in that the conclusion sets are distributed through a decision graph (41,42,43,46) of the database, the decision graph comprising a plurality of branch nodes at which a search key is matched with decision criteria in order to define which decision path should be taken through the decision graph, each conclusion set being reached by one, and only one, decision path through the decision graph; wherein conclusion sets are formed at some but not all of the branch nodes (41,46); and wherein the branch nodes at which conclusion sets are not formed define decision paths extending between the branch nodes at which conclusion sets are formed."

IX. Claim 1 of the first auxiliary request reads as follows:

"A method of organising storage of data in a database (2), in which conclusion sets (20, 24, 26, 28, 30; 40, 50, 60) for the database are arranged in a hierarchical structure with a plurality of levels, the conclusion sets storing the data which is stored in the database, and in which the conclusion sets are arranged such that items are inserted into a selected conclusion set at a first level until the number of items reaches a threshold value for the selected conclusion set, and then the contents of the selected conclusion set are migrated to subordinate conclusion sets, thereby emptying the selected conclusion set, and wherein following migration of the contents from the selected conclusion set, further insertions can be made into that conclusion set, characterised in that the conclusion sets are distributed through a decision graph (41,42,43,46) of the database, the decision graph comprising a plurality of branch nodes at which a search key is matched with decision criteria in order to define which decision path should be taken through the decision graph, each conclusion set being reached by one, and only one, decision path through the decision graph; wherein conclusion sets are formed at some but not all of the branch nodes (41,46); and wherein the branch nodes at which conclusion sets are not formed define decision paths extending between the branch nodes at which conclusion sets are formed."

X. Claim 1 of the second auxiliary request differs from claim 1 of the main request in the addition of the following text at the end of the claim:

", and further characterised in that the decision graph is constructed so as to maintain a specified inter conclusion set distance by:

establishing a first conclusion set (40) at the first level of significance (level 1);

establishing one or more temporary conclusion sets (44,45); and

migrating the contents of the first conclusion set (40) to the temporary conclusion set(s) until such time as a second conclusion set (50) is established at the specified inter conclusion set distance from the first conclusion set (40), whereupon the temporary conclusion set(s) are removed and their contents are moved to the second conclusion set."

XI. Claim 1 of the third auxiliary request differs from claim 1 of the first auxiliary request in the addition of the following text at the end of the claim:

", and further characterised in that the decision graph is constructed so as to maintain a specified inter conclusion set distance by:

establishing a first conclusion set (40) at the first level;

establishing one or more temporary conclusion sets (44,45); and

migrating the contents of the first conclusion set (40) to the temporary conclusion set(s) until such time as a second conclusion set (50) is established at the specified inter conclusion set distance from the first conclusion set (40), whereupon the temporary conclusion set(s) are removed and their contents are moved to the second conclusion set."

XII. The appellant's arguments can be summarised as follows.

The term "conclusion set" was not a commonly used term, but claim 1 of the main request defined exactly what conclusion sets were, and how they related to the decision graph. There was no standard universally used term for this feature.

The term "first level of significance" was clear. Claim 1 of the main request referred to a hierarchical structure, which was a tree-like structure using parent/child relationships. The concept of levels of significance was implicit in such a data structure.

Regarding inventive step, the appellant wished to formulate the problem as providing an alternative means of controlling the branching factor in a hierarchical structure of conclusion sets or alternatively as providing an alternative method of distributing conclusion sets through a decision graph. According to the jurisprudence of the boards of appeal it was not necessary for the application to state the problem. Both problems could have been easily deduced by a skilled person from the application as filed. Both problems were technical because they both impacted on the performance of the database. In particular, a narrow deep tree with a low branching factor was less efficient in terms of performing queries, because more nodes needed to be visited to reach the bottom of the tree. A shallow wide tree was less efficient in terms of update performance because the content of a parent conclusion set had to be distributed between more child conclusion sets. There was therefore a trade-off between these factors. The ability to control the branching factor hence provided a technical benefit and was not just an abstract concept. Distributing the conclusion sets sparsely enabled the effective branching factor of the conclusion sets to be changed without having to change the branching factor of the decision graph. A so-called conclusion set distance parameter Q could be used. If Q was set to 1, then each parent conclusion set led to 4 child conclusion sets, whereas if Q was set to 2, each parent conclusion set led to 8 child conclusion sets. However, in both cases each decision graph node had an individual branching factor of 2.

Reasons for the Decision

1. The appeal complies with the provisions referred to in Rule 101 EPC and is therefore admissible.

2. Main request - Article 84 EPC

2.1 It is common ground that the term "conclusion set" is not a standard term in the art. In the statement of the grounds of appeal, the appellant argued that this did not render claim 1 unclear, because the claim defined what conclusion sets were through the feature:

the conclusion sets storing data which matches search criteria or pointers which point to the location of the data which matches the search criteria.

The Board agrees with the decision under appeal that this definition is unclear. The definition states that conclusion sets store data or pointers to data and defines this data as data matching "search criteria". It is not clear what these "search criteria" are, as they are not mentioned elsewhere in the claim. Nor is it clear whether these "search criteria" are the same for all conclusion sets, or differ from conclusion set to conclusion set. In the latter case, the definition could be understood as defining which data records are stored in a particular conclusion set, namely those data records that match the search criteria corresponding to that conclusion set. In the former case, the definition appears to be merely a general statement that data records match certain undefined search criteria.

2.2 The Board further agrees with the decision under appeal that the expression "level of significance" is unclear, as the claim is silent on what kind of "significance" is meant.

In the statement of the grounds of appeal, the appellant submitted that the concept of levels of significance was implicit in a hierarchical data structure with parent/child relationships and that a parent had a higher level of significance than a child. However, the Board is not convinced that the parent node of a child node in a hierarchical data structure is commonly understood to have a "higher level of significance", and considers that this meaning of "significance" is also not clearly implied by the wording of the claim. On the contrary, the term "significance" could be understood to relate to the cognitive meaning of the data being stored.

2.3 It is further not clear in claim 1 how matching "data" with "search criteria" relates to matching a "search key" with "decision criteria".

2.4 In conclusion, the main request is not allowable for lack of clarity of claim 1 (Article 84 EPC).

3. First auxiliary request - Article 84 EPC

Claim 1 clearly defines the term "conclusion set" in that it defines conclusion sets as being the entities of the database in which data is stored and in that the features relating to the decision graph implicitly define which data is stored in which conclusion set. Since the claim does not refer to "levels of significance" and "search criteria", the objections raised in points 2.22.2 and 2.32.3 do not apply, either.

Claim 1 therefore meets the requirements of Article 84 EPC.

4. First auxiliary request - Articles 52(1) and 56 EPC

4.1 Claim 1 essentially defines a scheme of organising storage of data in a database which is a modification of prior-art schemes based on index trees such as B-trees. In these prior-art schemes, data records or pointers to data records are stored in the leaf nodes of a tree grouped by search key. Each internal (i.e. non-leaf) node of the tree stores information on the ranges of the search keys of the data records stored in each of the node's subtrees. Based on a search key, the corresponding data record is retrieved by starting at the root of the tree and iteratively selecting the subtree corresponding to the range of search keys that contains the search key of the data record to be retrieved until the leaf node storing the data record (or a pointer to it) is encountered.

The method according to claim 1 modifies these existing schemes by also allowing data records to be stored in internal nodes of the index tree. In the terminology of claim 1, the index tree is a "decision graph", its nodes are "branch nodes", and data records are allowed to be stored in internal nodes by "forming a conclusion set at a branch node". A new data record is inserted into the database by starting at the root of the tree and using its search key to follow a path towards a leaf node until a node with a conclusion set is encountered. If this conclusion set is not yet full (the number of items is below a threshold value), the data record is added to it. If it is full, its content is distributed over subordinate conclusion sets. This empties the conclusion set and allows further insertions to be made into it.

Claim 1 further defines that

(I) conclusion sets are formed at some but not all of the branch nodes, and that

(II) the branch nodes at which conclusion sets are not formed define decision paths extending between the branch nodes at which conclusion sets are formed.

It appears to the Board that feature (II) is not further limiting, but merely describes that conclusion sets are formed at a subset of the branch nodes of the decision graph, so that the remaining branch nodes form decision paths extending between the branch nodes of this subset.

4.2 Document D5, section 3 in combination with section 2.2, discloses a method of organising storage of data in a database using a tree-based index structure referred to as a "buffer-tree". Section 3.1 discloses that internal nodes and leaf nodes of the index tree, in addition to indexing information ("routing table"), comprise a buffer with at most p pages. Section 3.2 and figures 2 and 4-7 disclose that data records being inserted into the database are first stored in the buffer of an internal node until the buffer is full. When the buffer of an internal node is full, the buffer is cleared by redistributing its data records over the buffers of index nodes at a lower level of the index tree.

D5 is therefore a suitable starting point for the assessment of inventive step.

4.3 In a section titled "Obiter Dictum" of the decision under appeal, the difference between the claimed invention and the method of D5 was identified as consisting of features (I) and (II). In the statement of grounds of appeal, the appellant did not contest the Examining Division's analysis of D5. The Board considers that this analysis is also valid for the clarified claim 1 of the first auxiliary request.

4.4 In the statement of the grounds of appeal, the appellant submitted that the objective technical problem solved by distinguishing features (I) and (II) was to be formulated as providing an alternative means of controlling the branching factor in a hierarchical structure of conclusion sets. According to the appellant, the branching factor had a profound effect on the performance of the database. Alternatively, the appellant proposed the formulation providing an alternative method of distributing conclusion sets through a decision graph.

4.5 The Board is not convinced that features (I) and (II) in their generality solve the problem of controlling the branching factor and/or have a concrete effect on the performance of the database. This is because features (I) and (II) cover any distribution of conclusion sets over branch nodes, as long as a conclusion set is formed at some branch nodes and not at all branch nodes.

In the view of the Board, forming conclusion sets at all branch nodes except for one, e.g. the root node, constitutes a variation of the method of document D5 that is essentially arbitrary and does not provide any unexpected technical effect on the performance of the database.

This example also shows that features (I) and (II) do not solve the problem of controlling the branching factor, since leaving out one conclusion set does not affect the branching factor.

4.6 Features (I) and (II) do provide for an alternative distribution of conclusion sets over the decision graph, i.e. they solve the alternative problem proposed by the appellant. However, this problem formulation could be considered to contain a pointer to the solution, as it is essentially a restatement of features (I) and (II). Indeed, given that in D5 a conclusion set is formed at each branch node of the decision graph, the obvious solution to providing an alternative method of distributing conclusion sets through a decision graph is to form conclusion sets at some but not all of the branch nodes.

4.7 The Board therefore prefers to formulate the problem as that of providing a modification of the "buffer-tree" method of D5. However, also with this formulation the Board comes to the conclusion that the skilled person would arrive at the claimed invention without the exercise of inventive skill. Indeed, there is no technical reason why conclusion sets could only be formed either at none of the branch nodes (as in the prior-art schemes discussed in point 4.14.1 ) or at all of the branch nodes (as in D5). The skilled person would recognise that there are intermediate possibilities. Although the prior art might not provide a technical motivation for choosing such an intermediate scheme, the present application does not provide one either, at least not one applicable over the whole claimed scope. In the Board's view the skilled person therefore would, when looking for a technically arbitrary modification of the method of D5, consider using an intermediate scheme forming conclusion sets at some, but not all, of the branch nodes.

4.8 For these reasons the Board concludes that the subject-matter of claim 1 lacks an inventive step (Articles 52(1) and 56 EPC).

5. Second auxiliary request - Article 84 EPC

Claim 1 of the second auxiliary request corresponds to claim 1 of the main request with a number of further features added. Since these added features do not affect the clarity objections formulated in points 2.12.1 to 2.32.3 , the second auxiliary request is not allowable for lack of clarity of claim 1 (Article 84 EPC).

6. Third auxiliary request - Article 84 EPC

6.1 The feature "migrating the contents of the first conclusion set to the temporary conclusion set(s) until such time as a second conclusion set is established (...)" of claim 1 of the third auxiliary request is considered unclear.

6.2 Firstly, it is noted that the claimed method does not contain a step which would expressly result in the establishment of said second conclusion set.

From the description it appears that the "second conclusion set" of claim 1 is established by a step of "establishing one or more temporary conclusion sets". However, this is not expressed by the claim. In addition, this understanding of claim 1 is contradicted by the feature "whereupon the temporary conclusion set(s) are removed".

6.3 Secondly, it is not clear how the establishment of a single "second conclusion set" could allow the migration of the content of all temporary conclusion sets to that second conclusion set. In the normal case, the various temporary conclusion sets would contain data records that do not all match the search criteria on the path towards the second conclusion set.

6.4 Although these objections were communicated to the appellant in the communication accompanying the summons, the appellant has refrained from addressing them, e.g. by suitable amendment. The third auxiliary request can therefore not be allowed for lack of clarity of claim 1 (Article 84 EPC).

7. Since none of the requests is allowable, the appeal has to be dismissed.

Order

For these reasons it is decided that:

The appeal is dismissed.

Quick Navigation