T 1523/11 (Metadata index structure/SAMSUNG ELECTRONICS) of 17.1.2017

Summary of Facts and Submissions

I. The applicant (appellant) appealed against the decision of the Examining Division refusing European patent application No. 05075898.6, which was filed as a divisional of European patent application No. 03741584.1. The application claims an earliest priority date of 23 July 2002.

II. The decision cites inter alia the following documents:

D1: "SP003 V1.3 part B - System issues", cited by the Examining Division as Evain J.: "1st Draft of Metadata Specification SP003v1.3", 11 June 2002;

D3: Jagadish H. et al.: "On effective multi-dimensional indexing for strings", Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, June 2000, pp. 403-414;

D6: Böhm C. et al.: "Multidimensional index structures in relational databases", Journal of Intelligent Information Systems, Volume 15, Issue 1, July 2000, pp. 51-70;

D10: Kimball R.: "Kimball Design Tip #5: Surrogate Keys For The Time Dimension", 19 March 2000; and

D12: Garcia-Molina H. et al.: "Database System Implementation", 2000, ISBN: 0-13-040264-8.

The Examining Division decided that the subject-matter of claim 1 of a main request and of an auxiliary request lacked inventive step in view of a combination of document D1 and the common general knowledge of the skilled person as evidenced by documents D3, D6, D10 and D12.

III. With the statement of grounds of appeal, the appellant resubmitted copies of the main request and the auxiliary request considered in the contested decision.

IV. In a communication accompanying a summons to oral proceedings, the Board introduced the following documents:

D13: Evain J.: "1st Draft of SP003v1.3 (to be TV145)", 17 June 2002, 17th TV-Anytime meeting, 11-14 June 2002, Montreal;

D14: "Report of MD WG", 17th TV-Anytime meeting, 11-14 June 2002, Montreal;

D15: Millar K. et al.: "TV-Anytime contribution AN449: Encapsulation and indexing of XML document fragments (revised AN427)", 22 July 2002, 18th TV-Anytime meeting, 30 July-2 August 2002, Geneva;

D16: Shin H.: "AN448: An Indexing Scheme for Metadata Fragments featuring Multi-key Indexing and Fragment XPath Encoding", 23 July 2002, 18th TV-Anytime meeting, 30 July-2 August 2002, Geneva;

D17: Bibliographic details of XP030096119 (D13), XP030096126 (D14), XP030096136 (D15) and XP030096135 (D16);

D18: Kameyama W.: "A Uniform Resource Name (URN) Namespace for the TV-Anytime Forum", RFC4195, October 2005; and

D19: Ramakrishnan R. et al.: "Database Management Systems, Second Edition", 2000, pp. 237-244, ISBN: 0-07-244042-2.

The Board noted that documents D13, D14, D17 and D18 appeared to confirm that document D1 was part of the prior art under Article 54(2) EPC. It expressed the preliminary opinion that the subject-matter of claim 1 of both requests lacked inventive step in view of document D1 and the common general knowledge as evidenced by document D19. It further noted that documents D15 and D16 were potentially relevant to novelty and inventive step and that it intended, if necessary, to remit the case to the Examining Division to investigate whether those documents belonged to the prior art.

V. With a letter dated 16 December 2016, the appellant resubmitted copies of the main request and the auxiliary request as main request and first auxiliary request and filed second and third auxiliary requests.

VI. Oral proceedings took place on 17 January 2017 in the appellant's absence. At the end of the oral proceedings, the chairman pronounced the Board's decision.

VII. 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 or, in the alternative, on the basis of the claims of one of the first, second and third auxiliary requests.

VIII. Independent claim 1 of the main request reads as follows:

"An index structure for metadata arranged in a semistructured schema and divided into fragments as independently transmittable and individually accessible units of the metadata, wherein the index structure is for use in searching the metadata, the index structure comprising:

a key index list section (110);

a key index section (120); and

a sub-key index section (130);

characterised in that:

the key index list section (110) comprises a list of multi-keys, each multi-key corresponding to a combination of fields of the metadata; and

for each of the multi-keys of the key index list:

the sub-key index section (130) comprises ranges of values (114) of the multi-key and identification information on ones of the fragments of the metadata corresponding to the values (114) of the multi-key, and

the key index section (120) comprises a list of representative key values (113) representing the respective ranges of values (114) of the multi-key in the sub-key index section (130),

wherein with respect to comparison of the values (114) of the multi-key in size, the multi-key comprises fields (k1, k2, k3, ... kn) of the metadata which are prioritized (k1>k2>k3> ... kn), and the combined fields are compared in sequence, starting from a first field having a highest order of priority, wherein the values are compared on an arithmetic basis where the values of the multi-key are numerical or ranked in lexicographical order where the values of the multi-key are alphabetical."

IX. Independent claim 1 of the first auxiliary request differs from claim 1 of the main request in that the following text has been added at the end of the claim:

"wherein for two values of the multi-key (a1, a2, ..., an) and (b1, b2, ..., bn),

* the value of the multi-key (a1, a2, ..., an) is larger than the value of the multi-key (b1, b2, ..., bn) if and only if there exists an integer i (0<=i<=n-1) such that for every j(0<=j<=i-1), aj = bj and ai > bi,

* the value of the multi-key (a1, a2, ..., an) is smaller than the value of the multi-key (b1, b2, ..., bn) if and only if there exists an integer i (0<=i<=n-1) such that for every j(0<=j<=i-1), aj = bj and ai < bi,

* the value of the multi-key (a1, a2, ..., an) is equal to the value of the multi-key (b1, b2, ..., bn) if and only if for every i(1<=i<=n), ai = bi."

X. Independent claim 1 of the second auxiliary request differs from claim 1 of the main request in that after the text "each multi-key corresponding to a combination of fields of the metadata" the following text has been inserted:

"wherein the list of the multi-keys includes a location information of the fragment to which the field constituting the multi-key belong and location information of the field in the fragment"

The same amendment was made to claim 1 of the first auxiliary request to obtain independent claim 1 of the third auxiliary request.

XI. In so far as relevant to this decision, the appellant argued essentially as follows:

For a combination of prior-art disclosures to result in an obvious combination of features, the publications to be combined had to be from the same or a similar field and contain either a hint or incentive that problems of the closest prior art underlying the claim could be addressed by deploying the solution from the secondary prior art.

In the present case, however, document D1 related to searching metadata in a segmented stream in a transmission system, and document D19 related to searching in a database. It was far-fetched to assume that the skilled person in the field of document D1 would consult disclosures from the field of document D19.

In addition, document D19 contained no explicit disclosure of the feature of prioritising the fields or attributes. Consequently, that feature was not handed to the skilled person as a solution to any problem. It was precisely the prioritised arrangement of the metadata in the fields that allowed an improvement in efficiency and speed of the search.

Thus, the combination of documents D1 and D19 was based on hindsight; there was no reason why the skilled person would - rather than could - make the combination.

The features added in the auxiliary requests related to further improvements and were not known from document D19.

Reasons for the Decision

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

2. The application

2.1 The application relates to index structures for use in searching metadata, in particular XML metadata on digital content as defined by the TV-Anytime Forum. Such metadata is transmitted as independently transmittable and individually accessible fragments (see page 2, line 28, to page 3, line 10, of the application as filed).

2.2 The application refers on page 1, line 30, to page 2, line 2, and on page 4, lines 1 to 4, to a document titled "1st Draft of Metadata Specification SP003v1.3" (TV-Anytime Forum 17th meeting, Montreal, Canada), published in June 2002. This document is said to propose a "single key" index structure for a metadata fragment index. This structure is composed of a "key index list" section 10, "key index" sections 20 and "sub key index" sections 30 as shown in Figure 6 and described in particular on page 5, line 19, to page 7, line 20, of the application.

The "key index list" section 10 provides a list of all the single keys transmitted. It includes "single key information" defining each single key and "identification information" on the key index section 20 of the key (page 5, lines 27 to 30).

For each single key, the "key index" section 20 provides a list of "sub key index" sections 30. This list includes information "representing the range of values of the key included in the respective sub key index (sub_key_index) sections 30" in the form of a "representative key value" which is "the highest value of the key among the values of the key within the respective range". It also includes "identification information on the sub key index (sub_key_index) section 30 relevant to each representative key value" (page 6, lines 20 to 28).

Each "sub key index" section 30 includes inter alia 'key_value' segments 14 for storing "the respective ranges of values of the key" and 'target_container' and 'target_handle' segments for storing "respective" container identifier and fragment data identifier information. The latter two segments form identification information on the metadata fragments corresponding to the values of the key (page 7, lines 9 to 20).

2.3 This prior-art index structure works as follows. The purpose of the index structure is to efficiently find, on the basis of a key and a value of the key, the metadata fragments that "correspond" to that key value. For this purpose, the "sub key index" includes the possible values of the keys together with the identification information of the corresponding metadata fragments.

Since the number of possible values of a key may be large, a "key index" is provided on top of the "sub key index". Given a value of the key, this key index is used to quickly find the relevant portion of the sub- key index. For this purpose, the key index contains a subset of "representative values". Each of these values is the highest value of a range of values. The key index works as follows. Given an arbitrary value of the key, first the "representative value" is determined for the range to which the key belongs (i.e. the smallest of the representative values that is equal to or higher than that given value). The key index then provides the location of the corresponding range of values in the sub-key index.

Finally, since it may be useful if multiple indexes are available for searching the database, a "key index list" section is provided, listing the keys for which a key index section and corresponding sub-key index sections are provided.

2.4 The application stresses that the prior-art index structure is a "single key" index structure "which allows only one single key to be used for an access to the metadata" (page 4, lines 5 to 10). A single key index structure is said to be inefficient when performing a "compound condition search", i.e. a search on two or more fields (page 8, lines 8 to 14). As the application explains, in case of two conditions either each condition is independently searched by means of single key indexes and the intermediate results are intersected to obtain the final result (page 8, line 29, to page 10, line 16) or one condition is searched by means of a single key index and from the intermediate result those fragments are selected that satisfy the other condition (page 10, lines 17 to 22).

To improve the efficiency of compound condition searches the application proposes a "multi-key index structure".

3. Document D1

3.1 Document D1 bears the heading "SP003 V1.3 part B - System issues" but mentions neither an author nor a date. The Examining Division cited it as "1st Draft of Metadata Specification SP003v1.3", authored by "EVAIN J P" and published on 11 June 2002. It apparently assumed that it corresponded to the document cited in the application as disclosing a single key index structure (see point 2.2 above).

3.2 In the EPO's database, the Board has located document D13, which is another copy of the same document. Its bibliographic details suggest that document D1/D13 is indeed the document cited in the application and was published in June 2002 in connection with the 17th TV-Anytime Forum meeting (see document D17). These details are consistent with the information on "SP003v13" given on page 2 of document D14, which reports on the meeting.

3.3 The Board further notes that document D18 confirms that TV-Anytime Forum specifications at all stages of their development have been publicly available from the Internet address "ftp://tva:tva@ftp.bbc.co.uk/Specifications/" (page 2, section "Relevant ancillary documentation"). The Board notes that document D17 mentions the same address.

3.4 In view of these findings, the Board considers the content of document D1 to be part of the prior art under Article 54(2) EPC. The appellant has not contested this and in its letter of 16 December 2016 in fact stressed that it accepts the document's publication date to be 11 June 2002.

4. Main request - inventive step

4.1 It is undisputed that document D1 discloses the "single key index structure" for searching TV-Anytime metadata which is discussed in the application and summarised in point 2.2. 2 above. Document D1 indeed discloses in section 2.3 an index structure comprising a "key index list" (section 2.3.2), a "key index" (section 2.3.3) and a "sub key index" (section 2.3.4). The metadata is provided as an XML document (see section 2.3.1) and hence is "arranged in a semistructured schema".

4.2 The subject-matter of claim 1 of the main request differs from this prior-art single key index structure in that

- the keys are not single-attribute keys ("single keys") but multi-attribute keys ("multi-keys"); and

- values of a multi-key are compared by prioritising the fields (or attributes) making up the multi-key and comparing the fields in sequence starting from the field having the highest order of priority, wherein the values of a field are compared on an arithmetic basis if the field has numerical values or on a lexicographic basis if the field has alphabetical values.

4.3 The objective problem addressed by these features may be regarded as providing an efficient index structure for compound condition searches, i.e. searches on two or more fields.

4.4 According to the appellant, the skilled person starting from document D1 would not look for a solution to this problem in the technical field of database searching. The Board considers, however, that if the technical problem relates to index structures for searches, then the skilled person on the basis of whose knowledge and ability the obviousness of the solution is to be assessed is a person with knowledge of index structures, i.e. a person skilled in the field of database management systems (cf. decision T 26/98 of 30 April 2002, reasons 6.2 and 6.3). For the problem posed it is irrelevant that the metadata was retrieved in the form of a segmented stream.

4.5 The skilled person in the field of database management systems is well aware of the possibility of creating an index on a combination of multiple fields and he knows that such an index will speed up compound condition searches on those fields. Indeed, document D19, which is a textbook on database management systems and is illustrative of the common general knowledge of the skilled person, discusses in section 8.4.4 indexes for "composite" or "concatenated" search keys which contain several fields. The value of such a search key is a tuple of values of the combined fields.

The skilled person would therefore, on the basis of his common general knowledge, consider adapting the prior-art single-key index structure to work with such composite keys, i.e. multi-keys.

4.6 In doing so, the skilled person would realise that an order has to be defined on the values of multi-keys. Indeed, section 2.3.3 of document D1 explains that the key index structure lists the values of the highest key of each of the ranges of key values sorted by increasing key value, which means that it must be possible to say for any two key values which value is "higher". In the case of multi-keys these key values are tuples of values.

A well-known order on tuples of values is given by what is known in the computer-science literature as the "lexicographic order". This order is a generalisation of the alphabetic or lexicographic order on strings of characters (i.e. sort first on the first character, then on the second character, and so on). According to the lexicographic order on tuples of values, first the tuples are ordered by the value of their first ("highest priority") component; in case of a tie they are ordered by the value of the second component, and so on. In this comparison process, values of tuple components are compared in the normal way: if they are numerical values, they are typically compared on an arithmetic basis; if they are alphabetical values, they are typically compared lexicographically (i.e. alphabetically).

The examples given in section 8.4.4 of document D19 in fact silently use the lexicographic order on tuples: the values of the "<age, sal>" composite key are ordered (11, 80), (12, 10), (12, 20), (13, 75), i.e. first by age, then by salary ("sal"), and the values of the "<sal, age>" composite key are ordered (10, 12), (20, 12), (75, 13), (80, 11), i.e. first by salary, then by age. While the appellant is correct that document D19 does not "hand" the lexicographic order to the reader, the point is that document D19 presupposes that its skilled reader is well aware of the lexicographic order on tuples of values.

The order on multi-key values specified in claim 1 is in fact this lexicographic order on tuples.

4.7 Hence, the skilled person would adapt the prior-art single-key index structure to work with composite keys. In doing so, he would apply the lexicographic order when comparing values of multi-keys. He would thereby arrive at the subject-matter of claim 1 without the exercise of inventive skill.

4.8 In the statement of grounds of appeal, the appellant submitted that it is "precisely the prioritized arrangement of the metadata in the fields [that] allows an improvement in the search efficiency and speed" and that the prioritised order "allows a sequential search to yield results sooner (earlier in the sequence than half-way)".

However, in the application and in the claims the term "prioritization" refers merely to a ranking or ordering of the attributes that make up the multi-key. Such a ranking is necessary to define the lexicographic order on tuples of attribute values. The "prioritization" feature is thus part of the well-known "multi-key index" solution for speeding up compound condition searches.

4.9 Hence, the subject-matter of claim 1 lacks inventive step (Article 56 EPC).

5. First auxiliary request - inventive step

Since the features added to claim 1 of the auxiliary request merely repeat the definition of the order on multi-key values, the subject-matter of claim 1 likewise lacks inventive step (Article 56 EPC).

6. Second and third auxiliary requests - inventive step

6.1 Compared to claim 1 of the main request, claim 1 of the second auxiliary request adds that "the list of the multi-keys includes a location information of the fragment to which the field constituting the multi-key belong [sic] and location information of the field in the fragment". The same feature was added to claim 1 of the first auxiliary request to obtain claim 1 of the third auxiliary request.

Since the "key index list" section of the index structure of claim 1 comprises a "list of multi-keys" rather than "a multi-key", and since a multi-key corresponds to "a combination of fields" rather than "a field", the Board considers that the added feature is to be understood as meaning that the list of multi-keys includes location information for each field of each multi-key.

6.2 According to the background section of the application on page 5, line 27, to page 6, line 11, the "key index list" of the prior-art single key index structure includes "single key information" defining each single key. This single key information comprises "location information of the metadata fragment relevant to the single key" and "location information of the single key within the metadata fragment", corresponding to the "fragment_xpath_ptr" and "key_xpath_ptr" segments 11 and 12 shown in Figure 6.

The "key index list" described in section 2.3.2 of document D1 indeed includes, for each (single) key, such "fragment_xpath_ptr" and "key_xpath_ptr" information. Section 2.3.1.1 explains the meaning of the fragment Xpath and key Xpath information and confirms that the fragment Xpath locates the fragments of a particular type, whereas the key Xpath locates, relative to the node referred to by the fragment Xpath, the node corresponding to the field or attribute making up the "single key".

6.3 When adapting the single key index structure disclosed in document D1 to work with composite keys, the skilled person would adapt the location information accordingly and provide location information identifying the fragment and the field within the fragment for each field of each multi-key. He would thereby arrive at the subject-matter of claim 1 of the second and third auxiliary requests without the exercise of inventive skill.

6.4 Thus, the subject-matter of claim 1 of the second and third auxiliary requests lacks inventive step (Article 56 EPC).

7. Conclusion

Since none of the requests on file is allowable, the appeal is to be dismissed.

Order

For these reasons it is decided that:

The appeal is dismissed.