T 2539/12 (Searching a hierarchically structured database/SOFTWARE AG) 18-01-2018

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

Invention

2. The invention concerns the efficient searching of a hierarchically structured database for the results of "combined queries" comprising two or more conditions that must each be fulfilled for the same element. In one example, the database is in the form of an XML document and stores information about books (see e.g. original description, page 2, lines 15 to 25, and page 3, lines 7 to 10).

2.1 According to the description on page 2, lines 5 to 25, prior-art indexes are not adequate to perform some complex queries. The description gives an example of using the prior-art indexes to obtain the result of a search directed to books of the author "Jim Miller", i.e. first name = "Jim" and last name = "Miller", which results in books being found where the first name of one author is Jim and the last name of another is Miller. The purpose of the invention is to efficiently obtain the correct result for such queries.

2.2 According to the invention, the database includes elements, each element (e.g. corresponding to a book) comprising one or more hierarchically structured nodes for defining attributes of the element (e.g. first and last names of the author, chapter title and text). A unique identifier EID is assigned to each node of a plurality of selected nodes (page 7, lines 1 to 11, Figure 2). A reference index is created which assigns to each unique EID of a selected node the corresponding element of the database (page 7, lines 11 to 14, Figure 3). For nodes which can be the subject of search conditions of a query, search indexes are created which correlate the values of the nodes with the EIDs of ancestors of those nodes. A search index, also called "EID index" in the application, may be created for each search condition (page 7, lines 22 to 30, Figures 4 and 5).

2.3 A search for elements satisfying conditions c0, ci, ... is performed as described on page 8 with reference to Figure 6, in combination with original claims 1 and 2, essentially by

(d') retrieving a list L of EIDs of ancestor nodes for nodes satisfying the first search condition c0 using the EID index (i.e. the search index) corresponding to c0;

(e') for each further condition ci:

- investigating the EID index corresponding to the search condition ci to retrieve a further list Ei of EIDs of ancestor nodes for nodes which fulfil ci, and

- updating the list L by calculating its intersection with Ei, L := L intersection Ei;

(f') looking up the reference index for the EIDs in list L in order to obtain the searched elements.

2.4 The method of the invention is defined in claim 1 of the main request as comprising steps a to c, which are initial preparatory steps for assigning the unique identifiers and creating the reference and search indexes, and further steps d to f, corresponding to steps (d') to (f') described above, of actually performing a search.

Main request

3. Article 123(2) EPC

3.1 Compared to claim 1 as originally filed, claim 1 of the main request further refers to the "respective sub-attributes", is restricted to searches on the basis of "two or more search conditions", further defines step c of creating search indexes, and specifies in steps d and e that the retrieval of a set of identifiers is done by investigating the search index corresponding to the respective condition. Steps d and e have been reformulated when compared to the respective method steps of original claim 1.

3.1.1 The feature relating to "respective sub-attributes" in addition to attributes of the nodes finds support e.g. on page 1, lines 17 to 22. The restriction of the search to one based on "two or more", instead of "one or more", search conditions reflects the purpose of the invention as clearly disclosed e.g. on page 3, lines 7 to 10.

3.1.2 Step c of creating search indexes is described on page 7, lines 22 to 24. The combination of that step with the other features of the claim can be directly and unambiguously derived from that and other passages of the application as originally filed, e.g. page 8, lines 7 to 18, Figure 6 and claims 2 and 8.

3.1.3 Steps d and e of claim 1 are disclosed on page 8, lines 7 to 23, and in Figure 6. In particular, it is clear from those passages that the sets of unique identifiers are retrieved by investigating the search indexes as defined in steps d and e (Figure 6, steps 101 and 103).

3.2 Independent claim 6 is directed to a database and defines features corresponding to those of claim 1. Support for its subject-matter is the same as that given above for claim 1.

3.3 Dependent claims 2 to 5 and 7 to 10 correspond respectively to original claims 3, 4, 6, 7, 9, 10, 12 and 13 with some minor textual corrections.

3.4 The Board is therefore satisfied that the main request fulfils the requirements of Article 123(2) EPC.

4. Articles 84 and 83 EPC

4.1 In its communication, the Board raised several preliminary objections arising from the omission from the independent claims of features describing the search indexes and/or their use in the search method. Those deficiencies have been overcome by amendment, since independent claims 1 and 6 now define the search indexes and specify that a search index corresponding to a specific search condition is used in each of the steps of retrieving the sets of unique identifiers of ancestor nodes for nodes which fulfil the respective search condition.

4.2 In its preliminary opinion, the Board noted that the search conditions mentioned in the independent claims could apply to attributes of an element at different levels of the hierarchy. It seemed that in order to be able to correctly perform such queries, in particular to avoid the problem described on page 2, lines 15 to 25, of the description, some restrictions should apply with regard to the ancestor nodes. At the oral proceedings these issues were discussed in the context of sufficiency of disclosure and clarity.

4.2.1 In its reply and at the oral proceedings the appellant argued that the claimed method would work if there were a common ancestor of the nodes which were subject to search conditions. The nearest-common-ancestor node could be used. It was clear from the claim wording that the searchable nodes had a common ancestor. The skilled person would read the claim with a mind willing to understand and would exclude any interpretations that did not make sense. The skilled person would therefore interpret the claim as excluding a case in which there was no such common ancestor.

The Board agrees that the skilled person recognises that a common ancestor node is needed in order to obtain the correct search result and interprets the claim accordingly. As a special case, the skilled person implementing the method would also consider using the nearest-common-ancestor node in implementing searches. Even though the application does not describe in detail how the nearest-common-ancestor node should be used in the search method, the description on page 4, lines 25 to 28, refers to it as the "nearest ancestor node which occurs more than once" and suggests its use in the invention.

4.2.2 The appellant also argued that it was allowable for a claim to have a broader scope, even if the claimed solution would not work in isolated cases. The present invention provided a concept which had to be refined for specific cases. The essential steps of the invention were described. When implementing the method for a given situation, the skilled person would, using ordinary skills, select the appropriate ancestor nodes.

The Board recognises that the present invention provides a general solution to searching within elements of a hierarchically structured database for elements each fulfilling two or more search conditions, a general solution which has to be adapted to the particular database and searches to be performed. As explained on page 9, lines 14 to 15, in order to perform queries using the mechanisms of the invention, the database has to be prepared in advance. Steps a to c of claim 1 describe this preparatory phase in general terms, and the application on page 9, line 15, to page 10, line 18, describes some of the implementation details that are established in that phase. In particular, the database developer has to decide, on the basis of given requirements specifications regarding the particular database and the search queries and search conditions to be supported, to which nodes identifiers should be assigned and which search indexes are required (steps a and c of claim 1). Such a preparatory stage is standard practice in database systems.

The Board is of the opinion that it would not be possible to define the invention in more concrete and clear terms without unduly restricting the scope of protection. The teaching is applicable to different hierarchically structured databases and different searches of the type defined in the claim, i.e. searches for elements satisfying a plurality of search conditions.

4.3 Independent claim 6 specifies a database with a plurality of elements which is adapted to carry out a search comprising steps corresponding to steps d to f of claim 1. The plurality of elements are defined as comprising hierarchically structured nodes, a plurality of identifiers, a reference index and search indexes as defined in claim 1. The reasoning given above with regard to claim 1 therefore also applies to independent claim 6.

4.4 The other clarity issues discussed in the Board's preliminary opinion have been overcome by amendment.

The Board is therefore satisfied that the main request fulfils the requirements of Articles 83 and 84 EPC.

5. Inventive step

5.1 In the Board's opinion, it is clear from the wording of the claim that it concerns a computer-implemented method for searching for elements in a database stored in a computer, which uses data structures - the reference and search indexes - to access the data in the computer during the search. The claimed method therefore has technical character.

5.2 Document D1 is the closest prior art. It discloses a system for managing and searching a database of structured documents such as XML documents (paragraph [0008]).

The system of document D1 maintains the information on the XML documents in a relational database (paragraphs [0022] and [0023]). A structured document includes elements (e.g. document, sheet, page), and multiple instances of an element may occur in a document (see paragraphs [0023] and [0031], Figure 5). Unique element identifiers are associated with the element instances. For example, Figure 5 illustrates two instances of the document element, the first document with ID 1001 including two instances of the page element, page 1 with ID 1003 and page 2 with ID 1006.

The terminology of document D1 is different from that of the present application. The present application uses the term "element" only for root elements of the database such as "book" in the examples given in the application (see page 1, lines 13 to 22, page 7, lines 1 to 20). The elements in document D1 correspond to either elements or nodes in the language of the present application.

5.3 The relational database of the system described in document D1 comprises:

- a navigation table (Figure 2, table 20; Figure 6, table 212), and

- element tables (Figure 2, tables 24a, 24b, ... 24n; Figure 7, tables 216, 218, 220, 224 and 226).

5.3.1 The navigation table includes an entry for each element instance in the XML documents. It has three columns providing the unique identifiers of respectively the element instance, its parent and its root (paragraph [0025], Figure 2; paragraph [0032]). For example, the entry "1015, 1010, 1009" in navigation table 212 of Figure 6 provides the information that the element instance with the ID 1015 has the parent 1010 and the root 1009 (see Figure 5). The navigation table of document D1 hence corresponds to a reference index as defined in claim 1.

5.3.2 An element table is created for each different element, for example document, sheet, page, text and graphic object (see Figure 7). The element table for an element has a column for the unique element identifier and may have one column for each attribute value or content associated with that element. It stores an entry for each instance of that element in the XML documents, including its unique element identifier and the attribute values or content (see paragraph [0026], Figure 2; paragraph [0032], Figure 7).

An element table of document D1 is similar to a "search index" or "EID index" of claim 1. It differs from the search index in that it associates the values of nodes with the unique IDs of the corresponding nodes, not of ancestor nodes.

5.4 Document D1 describes a method for searching the database for XML documents "having element objects, e.g., attribute values or content, matching search criteria included in the query" (paragraph [0030], Figure 4), which as part of the result returns any document having any element object matching at least one of the criteria. It therefore does not solve the same problem as the present invention, that of the "combined queries" described in the present application and under points 2. and 2.1 above.

That method of document D1 includes steps for (see paragraph [0030] and Figure 4):

- determining an element table corresponding to the "element that is the subject of the query" (step 152),

- searching the element table to "find each entry having object data, e.g., attribute column value(s) or content, that satisfies the query search term(s)" (step 154),

- determining the element identifier for each entry in the element table having the matching object (step 156), and

- for each determined element identifier, obtaining from the navigation table the respective root identifier (step 158).

Step 158 seems to correspond to step f of claim 1. Steps 152 to 156 differ from steps d and e of claim 1 in that they investigate different indexes and retrieve identifiers of the nodes instead of ancestor nodes, and do not perform the intersection operation defined in step e.

In the decision under appeal, the Examining Division was of the opinion that document D1 in paragraph [0043] disclosed a step of retrieving identifiers of ancestor nodes. That paragraph mentions that "numerous other types of queries may be performed" and explains that, for instance, "after identifying element instances that satisfy a search criteria, the navigation table 20 may be used to identify the parent elements of the element instances having attribute values or content matching the search criteria".

That sentence does indeed suggest that ancestors are obtained for nodes which fulfil the search condition, but it does not describe that feature in the context of the method of Figure 4 and paragraph [0030]. Even if paragraph [0043] were considered to describe that feature in the context of the process of Figure 4, it would still be unclear in which phase of the process the unique identifiers of the parents would be retrieved and for what purpose.

5.5 The subject-matter of claim 1 differs from the method of document D1 in that the performed search is such that "one or more nodes of the searched element must fulfill two or more search conditions (c0, ci,..)" and in that it includes steps c to e.

Since the search indexes are data structures which provide access to stored data, the distinguishing features, which are based on the search indexes, contribute to the technical character of the claimed method (see e.g. T 1351/04 of 18 April 2007, reasons 7.2).

5.6 Document D1 discloses how to implement a search on the basis of search terms using the element and navigation tables, but does not disclose a concrete implementation of the type of search described in the claim.

The distinguishing features therefore solve the problem of implementing a search for elements each satisfying multiple search conditions on its nodes.

5.7 In the Board's opinion, starting from document D1 the skilled person faced with that problem would modify the method of D1 to perform the search for elements each satisfying multiple search conditions on its nodes using the element tables and navigation table. For example, the skilled person would consider using, at each iteration corresponding to each search condition, not only the element table for the specific search condition but also the navigation table in order to obtain the root identifiers corresponding to the entries found in the element table. Since the solution of document D1 is based on specific index structures, the skilled person would attempt to solve the problem of supporting new query types by modifying the steps of the method using the same index structures as before.

However, the solution of claim 1 is different to and more efficient than solutions based on the indexes of document D1, because it does not require additional steps of consulting the navigation table for each entry found.

The Board is not persuaded that it would be obvious for the skilled person, without a further hint, to modify the solution of document D1 by changing not only the method but also the indexes in the way of the distinguishing features in order to solve the problem addressed by the present invention.

None of the other cited prior-art documents gives such a hint. Document D2 describes the requirements for a query language for XML data. The queries disclosed on page 920, point (1) "Data match for select", cover the type of query described in the present application. However, document D2 describes only the query language, not the implementation of the queries. In particular, it does not mention indexes. The other cited prior-art documents are very remote from the claimed subject-matter.

5.8 From the above it follows that the subject-matter of claim 1 is inventive over the cited prior art and satisfies Articles 52(1) and 56 EPC. The same applies to corresponding independent claim 6 and the dependent claims.

Concluding remarks

6. The claims overcome all the objections raised in the proceedings, and the description has been adapted to the new claims. The Board is satisfied that the application complies with the requirements of the EPC. As a consequence, the appeal is to be allowed.

7. Even though in the grounds of appeal the appellant had argued that the reasoning of the decision under appeal was insufficient, it did not request reimbursement of the appeal fee. Following the Board's communication, the appellant did not further raise any objections concerning insufficient reasoning. In particular, it did not contest the Board's preliminary opinion that the reasoning of the decision under appeal was sufficient within the meaning of Rule 111(2) EPC. There is therefore no reason for the Board to further consider the reimbursement of the appeal fee.