T 1992/10 (Set identifiers / SAP) 08-09-2016
Download and more information:
Set identifiers for objects
I. This appeal is against the Examining Division's decision to refuse European patent application 05021811.4.
II. The Examining Division considered that the invention would have been obvious to the skilled person, starting from the combination of an RFID tag reader and a computer. The manipulations of the data, for which the invention provided, were held to be abstract data processing and, therefore, devoid of technical character.
III. With the statement setting out the grounds of appeal, the appellant maintained the three sets of claims underlying the impugned decision as main, first auxiliary, and second auxiliary requests. In a letter of response, dated 18 July 2016, to a communication sent with the summons to oral proceedings, the appellant re-submitted the main request, filed a new auxiliary request to replace the previous two, and presented supporting arguments.
IV. At oral proceedings, the appellant requested that the decision under appeal be set aside and that a patent be granted based on the main request or auxiliary request filed with letter of 18 July 2016.
V. Claim 1 according to the main request reads as follows.
A computer-implemented method for determining a set identifier for a group of physical objects, the method comprising:
- receiving (210), at a tag reader, a first identifier from a first identification tag (130a; 570a; 730a) associated with a first physical object (120a; 560a; 720a);
- receiving (220), at the tag reader, a second identifier from a second identification tag (130b; 570b; 730b) associated with a second physical object (120b; 560b; 720b);
- determining (230) the set identifier at the tag reader, the set identifier corresponding to a set (110) of physical objects that includes the first physical object (120a; 560a; 720a) and the second physical object (120b; 560b; 720b), based on the first identifier and the second identifier, wherein the determining further includes
-- sorting (440) the first identifier and the second identifier to produce sorted identifiers;
-- combining (450) the sorted identifiers to produce a combined set identifier by concatenating the first identifier and the second identifier in sorted order;
-- applying (460) a cryptographic hash function to the combined identifier to produce the set identifier; and
- associating (240-270) the set identifier with a virtual object (180a) that corresponds to the set (110);
- wherein the set identifier is effectively unique.
VI. Claim 1 according to the auxiliary request reads as follows
A computer-implemented method for checking the integrity of a shipment that includes multiple products, the method comprising:
calculating, prior to shipping, a set identifier for the shipment, the calculating comprising:
- receiving (210), at a tag reader, a first identifier from a first identification tag (130a; 570a; 730a) associated with a first physical object (120a; 560a; 720a);
- receiving (220), at the tag reader, a second identifier from a second identification tag (130b; 570b; 730b) associated with a second physical object (120b; 560b; 720b);
- determining (230) the set identifier at the tag reader, the set identifier corresponding to a set (110) of physical objects that includes the first physical object (120a; 560a; 720a) and the second physical object (120b; 560b; 720b), based on the first identifier and the second identifier, wherein the determining further includes:
-- sorting (440) the first identifier and the second identifier to produce sorted identifiers, such that, for all pairs of identifiers, a first identifier of a pair appearing before a second identifier of the pair indicates that the first identifier is less than the second identifier;
-- combining (450) the sorted identifiers to produce a combined set identifier by concatenating the first identifier and the second identifier in sorted order; and
-- applying (460) the SHA1 algorithm to the combined identifier to produce the set identifier;
- associating (240-270) the set identifier with a web page (180a) that corresponds to the set (110);
calculating a set identifier for the shipment after shipping to verify the integrity of the shipment;
when the set identifier calculated prior to shipping matches the set identifier calculated after shipping, determining that no products have been removed from or added to the shipment in the time between the calculation of the two set identifiers, and
when the set identifier calculated prior to shipping differs from the set identifier calculated after shipping, determining that at least one product has been removed from or added to the shipment in the time between the calculation of the two set identifiers.
VII. Those of the appellant's arguments that bear on this decision can be summarised as follows.
The set identifier was a functional data structure that enhanced the internal operation of a computer system and provided an RFID tag reader with additional functions, even if the reader was not changed. This was technical in view of T 467/03, Clipboard formats IV/MICROSOFT; and of T 513/98; neither published in the OJ EPO.
The steps of sorting, concatenating, and hashing served a technical purpose, because they had implications for logistics and access control; and because they were not just a series of instructions, but actual processes that caused physical changes within the computer. The association with a virtual object or web page was also technical. It was more than just a programming step, because it took place after all programming was finished; and more than a mental act, because it involved physical storage of the association in a technical data store, and because no human could or would calculate a cryptographic hash.
The invention had a number of advantages over the existing RFID system and over other possible implementations of set identifiers. A set identifier of the form according to the invention could be obtained and used without providing a separate tag for the set qua set. Moreover, it required no major changes to the communication protocols and databases. Rather, only the manner in which information was identified needed modification. Since the set identifier appeared in one column of a relational database, it was easy to access information about the whole set. That might otherwise be difficult to obtain, due to differing sizes of individual identifiers and large numbers of objects. When used in checking the integrity of shipments, both with and without the invention, it was necessary to scan all arriving objects; but with the invention, only one comparison needed subsequently to be made: the identifier calculated on arrival had to be compared with the identifier calculated before shipping. Without the invention, many individual comparisons would be needed.
Background
1. The invention concerns the identification of objects and of groups of objects. Each object is provided with a "tag", from which a "tag reader" can obtain an identifier. For the purpose of exposition, it is useful to think of the invention in terms of radio-frequency identification, "RFID", tags, with which every shopper is familiar. The invention is not limited to RFID, but the appellant relied on such a comparison with existing RFID when arguing in favour of inventive step.
2. The invention uses this infrastructure of object identifiers, and adds a way of forming an identifier for sets of objects. It might form an identifier for the set {A, B, ...} from the individual identifiers IDA, IDB, ....
3. The object identifiers are first sorted and are then concatenated so that, if IDA is "#0000AAA0000#" and IDB is "#0000BBB0000#", the combined identifier will be "#0000AAA0000##0000BBB0000#". The purpose of the sorting is that the concatenation is always done in a consistent way. Thus, it does not matter what ordering is used, so long as it is total (so that any two identifiers are comparable), and so long as it is the same order each time. The appellant regards these conditions as implicit.
4. After the concatenation, a cryptographic hash function is applied. The output of this is the identifier for the set. The significance of this is that an arbitrarily long string of identifiers is reduced to a relatively short identifier of fixed length, but in such a way that once an identifier for a particular set of objects has been obtained, it is very unlikely that another set can be found that produces the same hash value. That is the import of the term "effectively unique", used in claim 1 according to the main request.
5. In the main request, the set identifier is associated with a "virtual object". By this, the appellant means that some data store provides information about the set, and this information can be accessed using the set identifier. In the version according to the auxiliary request, the association is with a "web page", but the idea is essentially the same, because the web page also provides information about the set, accessed using the set identifier.
The two versions of claim 1
6. In claim 1 according to the main request, two identifiers are received at a tag reader. They are sorted, concatenated, hashed, and associated with a virtual object, as set out above.
7. In the auxiliary request, set identifiers, produced by the method of the main request, are used to check the integrity of a shipment. A set of objects is scanned before shipping, and their set identifier produced. The set of objects that arrive is scanned, and their set identifier is produced. If the same objects arrive as were sent, the two identifiers should match; but a match should be very unlikely if there is some discrepancy.
The approach to inventive step
8. The invention, as defined in claim 1 according to the main request, involves a combination of technical and non-technical features. The use of an identifier for sets of objects is not technical, as the appellant agreed. The steps of sorting, concatenating, and hashing constitute an algorithm which can be viewed either as a mathematical method or as a program for a computer. Either way, the algorithm as such is not technical and there is no need to consider the question of whether the steps could define a mental act, or to address the question of whether a human being could mentally calculate a hash function.
9. The appellant argued, however, that the use of an identifier for a set of objects did produce a technical effect, in its technical context (RFID tag readers and a relational database with a column for object identifiers), by increasing the speed with which information in the database can be retrieved. It further argued, that the steps of the algorithm also contributed to the fast look-up. If that is correct, and if the effect is indeed technical, then these features have the potential to contribute to inventive step.
10. This is not a case in which a clearly non-technical method, consisting of non-technical steps, is performed by a computer, essentially by telling it to carry out the steps involved. Such cases normally fail under the approach in T 0641/00, Two identities/COMVIK, OJ 2003, 352, which, by placing the steps in the statement of the objective technical problem, in essence ensures they do not contribute to inventive step. With such a method, the novelty and obviousness of the steps themselves need not be assessed and the salient question for inventive step is often only whether the implementation of the steps using a computer would have been obvious. In most cases, it would have been.
11. This contrasts with the present invention, in which, although the steps are per se non-technical, a technical contribution cannot be immediately ruled out. The need to investigate the obviousness of these steps depends on such a contribution. The aim of the invention is a non-technical one: identify objects and sets of objects, and keep track of them. The present invention, however, starts from an existing technical method of identifying objects. It seeks to overcome shortcomings in that technical method, and raises rather more problems than the cases referred to above. Are the shortcomings themselves technical? Are technical means used to overcome them? In short: what is the technical effect on the prior art system?
12. That is a matter that requires care. On one side, the technology of the starting point, or its shortcomings, should not be trivialised. On another, circumventing a problem, rather than solving it, is no basis for an allowable claim.
The main request
13. It is common ground that the tag and readers in the method according to claim 1 might be those in an RFID system. Indeed, it was part of the appellant's case, that such known readers and identifiers could continue to be used. What the invention purports to add is an ability to form identifiers for sets of objects from the identifiers of the individual objects.
14. There are two stages to consider. First, it must be decided to apply identifiers to sets rather than only to individual objects. Second, it must be decided how such set identifiers will be implemented. Conceivably, the order might be reversed: first the algorithm is devised, and it is subsequently realised that it can be used to produce identifiers for sets. If either of those paths would have been obvious, then the invention lacks inventive step.
15. The Board is persuaded that the first stage does not involve any technical consideration. An identifier for a set need be no more than a list of its contents or a general description. The books of J. K. Rowling, the first five symphonies of Beethoven, or the ancestors of Rhodri Mawr can be identified, as sets, by the terms just used or by simply listing the books, the symphonies, and the ancestors. Any effect on the speed of looking up information, depends on the form the identifiers take, how the information is recorded, and how it is retrieved. It is only after the second stage that these things are known.
16. As to the second stage, the appellant argued that the steps of sorting, concatenating, and hashing did not constitute a computer program in the sense of an abstract sequence of instructions. Rather, it was a sequence of operations physically carried out by the computer, which produced physical changes and which operated on, and produced, physical data.
17. The Board agrees that the performance of the steps by computer is a technical matter. At this level of analysis, however, the situation is as described under point 12., above.
18. The appellant also argued, at oral proceedings, that the steps of sorting, concatenating, and hashing involved the sorts of operation that computers could perform speedily, without, for example, accessing a database; and that when the database is consulted, the set identifier made the access faster.
19. The claim places no limits on the complexity of the sorting, concatenating, and hashing. The latter is "cryptographic", which means there is some lower bound to the complexity, but which says nothing about an upper bound. Thus, the algorithm may well be highly complex.
20. On the other hand, the step of "associating ... the set with a virtual object", might well be understood as referring to a mental act; but even accepting the appellant's argument that it meant an association stored by the computer, there is no implication of relative slowness. The association need not be in a database, let alone a database with a particular access structure; it could well be in the processor's own working memory. Indeed, that could still be the case even if the association was held there temporarily, pending later writing to persistent storage. In short, the appellant cannot rely on the putative slowness of database access technology.
21. The same applies to the appellant's further argument that the step of "associating" involves not only writing the data representing the association, but also, prior to that, checking that it is not already present. Firstly, although the description does support such checking (for example in paragraphs 33 - 35 of the published application), the claim makes no mention of it, and the invention it defines may operate without such a check. Secondly, the check need not be slow. It might be so in some, perhaps many, cases, but it need not be so. It may involve, as in paragraph 33 of the description, a "locally maintained mapping of set identifiers to virtual objects".
22. The Board, therefore, is not persuaded that the effect for which the appellant argued is actually obtained. Nor does the Board see the potential for any other technical effect.
23. The invention, then, consists of the prior-art method involving tag-readers and a computer for storing information, with the addition of further steps which have no technical effect. The absence of technical effect in the contribution over the prior art, means there is no inventive step.
24. It is worth noting that the appellant's argument, that the steps of the algorithm were not a computer program but were concrete actions performed by a machine, plays no role here. It is already established that the claimed method, implemented on a computer, is technical. There is no doubt that when instructions are carried out, the computer produces technical effects. But those effects are inevitable, once the non-technical decision to use a particular non-technical algorithm has been made.
25. It is also worth noting that there is a parallel with T 0467/03. In that decision, a computer running Windows 3.1 provided certain functionality (drag/drop, cut/paste) using the clipboard format. The invention extended those functions, so that more things could be cut and pasted. In the present case, the functionality of the composite of tag readers and computer system is extended. That is why the Board found it necessary to look for some technical effect in the first and second stages mentioned above. There is no parallel, however, between the situation in T 0467/03 and the implementation of the algorithm on the computer in the present invention. The algorithm does not seek to overcome a limitation of a computer, but is imposed from outside for the non-technical purpose of providing a set identifier.
The auxiliary request
26. This request can be dealt with more succinctly. The appellant accepted that the context of shipping, and the change from association with a virtual object to association with a web page, did not provide any technical effects beyond those already inherent in the invention according to claim 1 of the main request.
27. The appellant's argument was, rather, that the context of checking integrity rendered the technical effects inherent in the main request clearer. In particular, the step of comparing the identifier obtained on arrival with the identifier obtained prior to shipping, involved a further look-up in the database; but while this was a slow operation, it was only one slow operation because there was only one identifier for the whole set. A look-up of each of the constituent objects would involve several slow operations.
28. The Board finds this argument unpersuasive. Firstly, it is predicated on assumptions about the database access for which neither the claim nor the description provides a basis. A database programmer would, for example, tend to send one composite query, rather than a series of individual queries. However that may be, as already noted, there need be no database involved at all in the step of associating, and the same goes for the steps involving comparison: there are many ways in which the identifier obtained prior to shipping could be conveyed to the point of comparison. What is important to the invention is that the identifiers before and after should be the same and that a comparison can be made. Neither the claim nor the description sets out the means of conveyance to the point of comparison.
29. Even more can be said, because even if there is a database, and even if access to it is very slow, the check on integrity does not involve looking up information about the set. The identifiers are not found by looking in a database; rather, they are the information needed to find other information in the database, if such information is sought. In this version of the invention, no information is sought other than the two set identifiers which are, hopefully, the same.
30. The Board, therefore, sees no more of a technical effect than it sees in the main request. Accordingly, the Board sees no inventive step in the invention according to claim 1 of the auxiliary request.
For these reasons it is decided that:
The appeal is dismissed.