Relation path viability prediction

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.

What is claimed is: 
     
       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.   
     
     
       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. 
   
     
     
       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. 
     
     
       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.   
     
     
       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.   
     
     
       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.   
     
     
       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. 
     
     
       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. 
     
     
       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. 
     
     
       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. 
     
     
       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.   
     
     
       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. 
     
     
       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. 
     
     
       42. The method of claim 37, wherein said instance-to-object bitmap is used to predict whether a query will produce a result. 
     
     
       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.