Relation path viability prediction

• US RE45,752 E1
• Filed: 12/29/2004
• Issued: 10/13/2015
• Est. Priority Date: 07/02/1999
• Status: Expired due to Term

• Current Assignee: Sap Portals, Inc. (SAP SE)
• Original Assignee: Sap Portals Israel Ltd (SAP SE)
• Inventors: Agassi, Shai, Gvily, Yaniv
• Primary Examiner(s): AL HASHEMI, SANA A
• Application Number:
  US11/027,585
• Time in Patent Office: 3,940 Days
• Field of Search: 707/688, 707/692, 707/699, 707/999.103, 707/781, 707/954, 707/960, 707/956
• US Class Current: 1/1
• CPC Class Codes: G06F 16/2237 Vectors, bitmaps or matrices
• CPC Class Codes: G06F 16/2428 Query predicate definition using graphical user interfaces, including menus and forms G06F16/2423 takes precedence
• CPC Class Codes: G06F 16/24532 of parallel queries
• CPC Class Codes: G06F 16/24539 using cached or materialised query results
• CPC Class Codes: G06F 16/24545 Selectivity estimation or determination
• CPC Class Codes: G06F 16/2457 with adaptation to user needs
• CPC Class Codes: G06F 16/248 Presentation of query results
• CPC Class Codes: G06F 16/289 Object oriented databases
• CPC Class Codes: G06F 17/30445 for parallel queries
• CPC Class Codes: Y10S 707/99935 Query augmenting and refining, e.g. inexact access
• CPC Class Codes: Y10S 707/99943 Generating database or data structure, e.g. via user interface

Abstract

There is provided a process for predicting whether a query will produce a result in an information system formed of objects having different instances and relations between the objects. An instance-to-object bitmap is computed off-line, before queries are generated by a user: the bitmap is used to represent the existence of a relation path from instances to the other objects of a database. When a query is generated, the bitmap is accessed to predict whether there exists a relation from the instance to the object, that is whether the query will issue a result. The process makes it possible for a user to abort queries without consuming run-time. It also makes it possible to guide users through navigation of a Webpage or the like, by suggesting relations that will produce results.

Claims

1. In an information system comprising objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, a method for predicting whether a query will produce a result, the method comprising the steps of:

providing an instance-to-object bitmap which indicates whether instances of objects are related to other objects; and

accessing the bitmap to determine if the query will produce a result.

2. The method of claim 1, wherein the step of providing an instance-to-object bitmap comprises generating the instance-to-object bitmap by:

computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object; and

computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object.

3. The method of claim 2, wherein the step of computing a path from an instance to a non-neighboring object is repeated.

4. The method of claim 2, wherein the step of computing a path from an instance to a non-neighboring object is repeated until relation paths of a predetermined length are computed.

5. The method of claim 3, wherein the step of providing an instance-to-object bitmap comprises providing an instance-to-object bitmap which indicates whether each instance of an object is related to all other objects by a relation path having a length equal to or lower than a predetermined length.

6. The method of claim 1, wherein the step of providing comprises providing an instance-to-object bitmap indicating whether each instance of an object is related to all other objects by a relation path having a length equal to or lower than a predetermined length.

7. An information system comprising objects, instances of said objects, relationships between at least some of said objects and said instances of said objects, and an instance-to-object bitmap indicating whether instances of objects are related to other objects.

8. The information system of claim 7, wherein said instance-to-object bitmap indicates whether an instance of an object is related to other objects by a relation path having a length equal to or lower than a predetermined length.

9. The information system of claim 7, further comprising means for aborting a query from an instance to an object when said instance-to-object bitmap indicates that the instance is not related to the object.

10. The information system of claim 7, further comprising a data navigator interface with at least a draggable element and at least a drop target, a query being generated when a draggable element is dragged and droped onto a drop target.

11. The information system of claim 10, further comprising means for aborting said query when said instance-to-object bitmap indicates that the draggable element is not related to the drop target.

12. The information system of claim 10, further comprising means for displaying on said interface that a query will not produce any result when said instance-to-object bitmap indicates that the draggable element is not related to the drop target.

13. In an information system comprising objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, a method for generating an instance-to-object bitmap, comprising the steps of;

computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object; and

computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object.

14. The method of claim 13, wherein the step of computing a path from an instance to a non-neighboring object is repeated.

15. The method of claim 13, wherein the step of computing a path from an instance to a non-neighboring object is repeated until relation paths of a predetermined length are computed.

16. The method of claim 15, wherein said instance-to-object bitmap is used to predict whether a query will produce a result.

17. In an information system comprising objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, a method for predicting a likelihood of whether a query will produce a result, the method comprising the steps of:

providing an object-to-object probability matrix, which indicates a likelihood that an instance of an object is related to another object; and

accessing the probability matrix to determine a likelihood that the query will produce a result.

18. The method of claim 17, wherein the step of providing an object-to-object probability matrix comprises generating the object-to-object probability matrix by:

for each object, computing a probability that an instance in an object is related to a neighboring object; and

computing probabilities that instances in objects are related to non-neighboring objects using the probabilities computed in the previous step.

19. The method of claim 18, wherein the step of computing a probability that an instance in an object is related to a neighboring object comprises:

determining a number of instances in a first object related to a neighboring second object; and

calculating the probability that an instance in said first object is related to said neighboring second object by dividing the number of instances in said first object related to said neighboring second object by a total number of instances in said first object.

20. The method of claim 19, wherein the step of computing probabilities that instances in objects are related to non-neighboring objects comprises:

computing a first probability that an instance in a first object is related to a second object, said second object neighboring said first object;

computing a second probability that an instance in said second object is related to a third object, said third object neighboring said second object; and

computing a third probability that said first object is related to said third object, said third object not neighboring said first object, by multiplying said first probability by said second probability.

21. The method of claim 19, wherein the step of determining a number of instances in a first object that are related to a second object comprises using an instance-to-object bitmap to determine which instances of said first object are related to said second object.

22. The method of claim 21, wherein said instance-to-object bitmap is generated by:

computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object; and

computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object.

23. The method of claim 22, wherein the step of computing a path from an instance to a non-neighboring object is repeated.

24. A method for predicting when a query will produce a result, comprising:

in an information system with objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, wherein at least one relationship is an indirect relationship which is determined from indirectly related references to said objects, providing a set of instance-to-object relations which indicates whether instances of objects are related to other objects;

accessing the set to determine when the query will produce a query result; and

outputting a result of the determination.

30. The method of claim 24, wherein the step of providing comprises providing an instance-to-object bitmap indicating whether each instance of an object is related to all other objects by a relation path having a length equal to or lower than a predetermined length.

25. In an information system comprising objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, a method for predicting whether a query will produce a result, the method comprising the steps of:

providing an instance-to-object bitmap which indicates whether instances of objects are related to other objects; and

accessing the bitmap to determine if the query will produce a result;

wherein the step of providing an instance-to-object bitmap comprises generating the instance-to-object bitmap by;

computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object; and

computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object.

31. The method of claim 25, wherein the step of computing a path from an instance to a non-neighboring object is repeated.

32. The method of claim 25, wherein the step of computing a path from an instance to a non-neighboring object is repeated until relation paths of a predetermined length are computed.

39. The method of claim 31, wherein the step of providing an instance-to-object bitmap comprises providing an instance-to-object bitmap which indicates whether each instance of an object is related to all other objects by a relation path having a length equal to or lower than a predetermined length.

26. An information system comprising objects, instances of said objects, relationships between at least some of said objects and said instances of said objects wherein at least one relationship is an indirect relationship which is determined from indirectly related references to said objects, an instance-to-object bitmap indicating whether instances of objects are related to other objects;

and a server for outputting the instance-to-object bitmap in a computer-readable form.

33. The information system of claim 26, wherein said instance-to-object bitmap indicates whether an instance of an object is related to other objects by a relation path having a length equal to or lower than a predetermined length.

34. The information system of claim 26, further comprising means for aborting a query from an instance to an object when said instance-to-object bitmap indicates that the instance is not related to the object.

35. The information system of claim 26, further comprising a data navigator interface with at least a draggable element and at least a drop target, a query being generated when a draggable element is dragged and dropped onto a target.

40. The information system of claim 35, further comprising means for aborting said query when said instance-to-object bitmap indicates that the draggable element is not related to the drop target.

41. The information system of claim 35, further comprising means for displaying on said interface that a query will not produce any result when said instance-to-object bitmap indicates that the draggable element is not related to the drop target.

27. A method for generating an instance-to-object bitmap, comprising:

in an information system with objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, wherein at least one relationship is an indirect relationship which is determined from indirectly related references to said objects, computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object;

computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object; and

outputting the instance-to-object bitmap that reflects results of the computed paths.

36. The method of claim 27, wherein the step of computing a path from an instance to a non-neighboring object is repeated.

37. The method of claim 27, wherein the step of computing a path from an instance to a non-neighboring object is repeated until relation paths of a predetermined length are computed.

42. The method of claim 37, wherein said instance-to-object bitmap is used to predict whether a query will produce a result.

28. A method for predicting a likelihood of when a query will produce a query result, comprising:

in an information system with objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, wherein at least one relationship is an indirect relationship which is determined from indirectly related references to said objects, providing an object-to-object probability matrix, which indicates a likelihood that an instance of an object is related to another object;

accessing the probability matrix to determine the likelihood the query result will be produced by the query; and

outputting a result of the accessing, representing the likelihood.

38. The method of claim 28, wherein the step of providing an object-to-object probability matrix comprises generating the object-to-object probability matrix by:

for each object, computing a probability that an instance in an object is related to a neighboring object; and

computing probabilities that instances in objects are related to non-neighboring objects using the probabilities computed in the previous step.

43. The method of claim 38, wherein the step of computing a probability that an instance in an object is related to a neighboring object comprises:

determining a number of instances in a first object related to a neighboring second object; and

calculating the probability that an instance in said first object is related to said neighboring second object by dividing the number of instances in said first object related to said neighboring second object by a total number of instances in said first object.

44. The method of claim 43, wherein the step of computing probabilities that instances in objects are related to non-neighboring objects comprises:

computing a first probability that an instance in a first object is related to a second object, said second object neighboring said first object;

computing a second probability that an instance in said second object is related to a third object, said third object neighboring said second object; and

computing a third probability that said first object is related to said third object, said third object not neighboring said first object, by multiply said first probability by said second probability.

45. The method of claim 43, wherein the step of determining a number of instances in a first object that are related to a second object comprises using an instance-to-object bitmap to determine which instances of said first object are related to said second object.

46. The method of claim 45, wherein said instance-to-object bitmap is generated by:

computing paths from instances to neighboring objects by determining a path from an instance in an object to an instance in a neighboring object; and

computing a path from an instance to a non-neighboring object by merging a path from an instance in a first object to an instance in a second object with a computed path from said instance in said second object to said non-neighboring object.

47. The method of claim 46, wherein the step of computing a path from an instance to a non-neighboring object is repeated.

29. A computer-readable medium containing program code and data structures comprising:

in an information system with objects, instances of said objects and relationships between at least some of said objects and said instances of said objects, wherein at least one relationship is an indirect relationship which is determined from indirectly related references to said objects, at least one data structure representing a set of instance-to-object relations that indicates whether instances of objects are related to other objects;

program code for accessing the set to determine when the query will product a query result; and

program code for outputting a result of the determination.