Querying an object-oriented data hierarchy using relational query languages

Abstract

A novel system, computer readable storage medium and method for creating re-usable queries over complex data including hierarchies, trees and graphs is described. This is achieved by an object-oriented query language, where a class is a logical property of a data item, and inheritance is implication between such properties. Virtual method calls execute all relevant method implementations in most specific classes. Expressions can be multi-valued, thus avoiding the need for naming intermediate results. All constructs closely follow the syntax of mainstream object-oriented languages like Java.

What is claimed is: 
     
       1. A process for creating re-usable queries over complex data, the process comprising:
 defining a re-usable object-orientedreceiving queries defined in a first query language within which logical properties are represented by object-oriented classes treated as logical properties, wherein each logical property is defined by one or more specified classes of at least one complex data itemand in which inheritance relationships between the classes represent relationships between the logical properties, and wherein the queries include requests for data items having requested logical properties; 
 relating inheritance, used to form new class with the specified classes, to the logical properties along with a plurality of virtual method calls that execute all applicable method implementations in at least one of the specified classes; and 
 in response to the queries requesting data items having logical properties encoded as methods of particular classes, dispatching on the logical propertiesparticular classes to choose at least oneone or more most specific implementationimplementations of an operationthe methods, wherein a most specific implementation of a method is in a class where no subclasses define a same methodother classes that inherit from the class include an implementation of the method, wherein the dispatching on the logical propertiesparticular classes further includes:
 definingidentifying a named predicate p as predicate p(T 1 x 1 , . . . , T n x n ) {formula} for each one of the applicable methodmost specific implementations, wherein the named predicate p has variables x 1 , . . . , x n . so as to restrict a range of a relation, which contains tuples (x 1 , . . . x n ) where each x i  has a type TT i ;   testing a receiver against each relevant type and choosing the applicable method implementations from the most specific implementations, wherein testing a type of the receiver is achieved by includes invoking a named constructor for each class defining a method of a relevant signature most specific implementation, regardless of static types;   implementing queries by translating actual or possibly recursive object-oriented the queries to a second query language using for each method and constructor of each class, a first special variable that holds a value that is a member of the class, and for each method that is not a predicate, a second special variable that holds a result of a method; and   rendingrendering the queries concise by at least using multi-valued operations to avoid naming intermediate results in nested method calls.   
 
     
     
       2. The process as set forth in  claim 1 , wherein translating the implementing queries includes mapping each constructor to a named characteristic predicate of its class, which tests whether a value belongs to the class, by taking a logical conjunction of characteristic predicates of all superclasses and a property specified in the constructor. 
     
     
       3. The process as set forth in claim  1  2, wherein translating the implementing queries includes mapping instanceof tests and cast expressions to calls of such each characteristic predicates. 
     
     
       4. The process as set forth in  claim 1 , wherein translating the implementing queries includes mapping expressions including nested method calls to a conjunction of predicate calls, with a new named variable denoting an intermediate result of each method call. 
     
     
       5. The process as set forth in  claim 1 , wherein the implementing queries by translating actual or possibly recursive object-oriented the queries to the second query language produces queries in Datalog and wherein at least one search engine is targeted by translating a same intermediate Datalog to different executable formats. 
     
     
       6. The process as set forth in  claim 1 , wherein rendering the queries are rendered concise by includes at least one of:
 using a * notation and a + notation on multi-valued operations to indicate a chained application of such operations; and or  
 using an aggregate notation with variables, a range condition and an expression (agg(vars|condition|expr)). 
 
     
     
       7. The process as set forth in  claim 1 , wherein complex data at least one of the data items is stored in a standard relational database data storage, and column types are used to build a hierarchy of object-oriented classes on top of an existing relational database, by annotating an existing relational schema relationships between the logical properties are identified in a data format definition for the data storage storing the data item. 
     
     
       8. The process as set forth in  claim 1 , wherein at least one of the data items is a complex data item is at and includes least one of:
 a data item in a hierarchy; 
 a tree; and or  
 a graph. 
 
     
     
       9. The process as set forth in  claim 1 , wherein an object-oriented query language is in any form depending on a domain of object-oriented query language use, including instructions in the first query language are represented in at least one of:
 a textual form; 
 a graphical form; 
 a query-by-example user interface form; and or an  
 embedded in a more general form within another programming language. 
 
     
     
       10. The process as set forth in claim  1  7, wherein complex data is stored in a plurality of datasource formats including the data storage includes at least one of:
 a relational database; 
 a web service; 
 a web page; and or  
 a structured data file on hard disk and column types are used to build a hierarchy of object-oriented classes on top of such data formats, by annotating each relevant data format schema. 
 
     
     
       11. A computer program product for creating re-usable queries over complex data, the computer program product comprising:
 a non-transitory computer readable storage medium, the non-transitory computer readable storage medium storing software programming instructions capable of performing with a processor programming code to carry out: 
 defining a re-usable object-orientedreceiving queries defined in a first query language within which logical properties are represented by object-oriented classes treated as logical properties, wherein each logical property is defined by one or more specified classes of at least one complex data itemand in which inheritance relationships between the classes represent relationships between the logical properties, and wherein the queries include requests for data items having requested logical properties; 
 relating inheritance, used to form new class with the specified classes, to the logical properties along with a plurality of virtual method calls that execute all applicable method implementations in at least one of the specified classes; and 
 in response to the queries requesting data items having logical properties encoded as methods of particular classes, dispatching on the logical propertiesparticular classes to choose at least oneone or more most specific implementationimplementations of an operationthe methods, wherein a most specific implementation of a method is in a class where no subclasses define a same methodother classes that inherit from the class include an implementation of the method, wherein the dispatching on the logical propertiesparticular classes further includes:
 definingidentifying a named predicate p as predicate p(T1x1, . . . , Tnxn) {formula} for each one of the applicable methodmost specific implementations, wherein the named predicate p has variables x1, . . . , xn so as to restrict a range of a relation, which contains tuples (x1, . . . , xn) where each xi has a type Ti;   testing a receiver against each relevant type and choosing the applicable method implementations from the most specific implementations, wherein testing a type of the receiver is achieved by includes invoking a named constructor for each class defining a method of a relevant signature most specific implementation, regardless of static types;   implementing queries by translating actual or possibly recursive object-oriented the queries to a second query language using for each method and constructor of each class, a first special variable that holds a value that is a member of the class, and for each method that is not a predicate, a second special variable that holds a result of a method; and   rendingrendering the queries concise by at least using multi-valued operations to avoid naming intermediate results in nested method calls.   
 
     
     
       12. The computer program product of  claim 11 , wherein translating the implementing queries includes mapping each constructor to a named characteristic predicate of its class, which tests whether a value belongs to the class, by taking a logical conjunction of characteristic predicates of all superclasses and a property specified in the constructor. 
     
     
       13. The computer program product of claim  11  12, wherein translating the implementing queries includes mapping instanceof tests and cast expressions to calls of such each characteristic predicates predicate. 
     
     
       14. The computer program product of  claim 11 , wherein translating the implementing queries includes mapping expressions including nested method calls to a conjunction of predicate calls, with a new named variable denoting an intermediate result of each method call. 
     
     
       15. The computer program product of  claim 11 , wherein the implementing queries by translating actual or possibly recursive object-oriented the queries to the second query language produces queries in Datalog and wherein at least one search engine is targeted by translating a same intermediate Datalog to different executable formats. 
     
     
       16. An information processing system for creating re-usable queries over complex data, the system comprising:
 a computer memory capable of storing machine instructions; and 
 a processor in communication with said computer memory, said processor configured to access the memory, the processor performing 
 a re-usable object-oriented query language defined with object-oriented classes treated as logical properties, wherein each logical property is defined by one or more specified classes of at least one complex data item; 
 a new class formed by relating inheritance with the specified classes, to the logical properties along with a plurality of virtual method calls that execute all applicable method implementations in at least one of the specified classes; and and execute the machine instructions to perform operations comprising:  
 receiving queries defined in a first query language in which logical properties are represented by object-oriented classes, and in which inheritance relationships between the classes represent relationships between the logical properties, and wherein the queries include requests for data items having requested logical properties;  
 means forin response to the queries requesting data items having logical properties encoded as methods of particular classes, dispatching on the logical propertiesparticular classes to choose at least one or more of a most specific implementation implementations of an operation the methods, wherein a most specific implementation of a method is in class where no subclasses define a same method other classes that inherit from the class include an implementation of the method, wherein the dispatching on the logical properties particular classes further includes:
 means for definingidentifying a named predicate p as predicate p(T 1 x 1 , . . . T n x n ) {formula} for each one of the applicable methodmost specific implementations, wherein the named predicate p has variables x 1 , . . . x n . so as to restrict a range of a relation, which contains tuples (x 1 , . . . , x n ) where each x 1  has a type T i ; 
 means for testing a receiver against each relevant type and choosing the applicable method implementations from the most specific implementations, wherein testing a type of the receiver is achieved by includes invoking a named constructor for each class defining a method of a relevant signature most specific implementation, regardless of static types; 
 means for implementing queries by translating actual or possibly recursive object-oriented the queries to a second query language using for each method and constructor of each class, a first special variable that holds a value that is a member of the class, and for each method that is not a predicate, a second special variable that holds a result of a method; and 
 means for rendingrendering the queries concise by at least using multi-valued operations to avoid naming intermediate results in nested method calls. 
 
 
     
     
       17. The system of  claim 16 , wherein translating the implementing queries includes mapping each constructor to a named characteristic predicate of its class, which tests whether a value belongs to the class, by taking a logical conjunction of characteristic predicates of all superclasses and a property specified in the constructor. 
     
     
       18. The system of claim  16  17, wherein translating the implementing queries includes mapping instanceof tests and cast expressions to calls of such each characteristic predicates. 
     
     
       19. The system of  claim 16 , wherein translating the implementing queries includes mapping expressions including nested method calls to a conjunction of predicate calls, with a new named variable denoting an intermediate result of each method call. 
     
     
       20. The system of  claim 16 , wherein the implementing queries by translating actual or possibly recursive object-oriented the queries to the second query language produces queries in Datalog and wherein at least one search engine is targeted by translating a same intermediate Datalog to different executable formats.