Method and system for generating string-based addresses

A method and system are described that may generate and process address strings, for example, for database entities such as objects. An example method may include generating a first address string representing a first relational path associated with a first database query retrieval of a first object, and storing the first address string in association with the first object. Another example method may include receiving a query requesting information associated with an entity related to one or more objects included in a database. The method may further include retrieving a first address string based on a search of address strings to determine address strings that indicate the entity, the first address string representing a first relational path associated with a database query retrieval of a first object, and retrieving the first object based on the retrieved first address string.

TECHNICAL FIELD

This description relates to information storage and retrieval techniques.

BACKGROUND

Storing and retrieving information quickly and efficiently has conventionally been a challenge, for example, with respect to business tasks in companies. As databases have expanded, computing power has increased, and storage costs have gone down. Conventional storage and retrieval techniques have focused on minimizing storage requirements, sometimes at the expense of higher computing times.

With regard to conventional relational databases, records or database objects may be stored in tables based on a unique identifier for each record or object. Database entities may be related to each other via various relationships which may be reflected, for example, via columns having common names. For example, a “person” object may include a particular set of “person” attributes, and the “person” may include an “is-a” relationship with a “manager” entity. The “manager” may have a “manager-of” relationship with another “person” object. Thus, there may exist an object hierarchy such that a meaningful response to a query may require a navigation of an object tree which may involve retrieving objects at each node of the navigation, which may be very time-consuming.

For example, when a user submits a query to a relational database system, the database system may process the query by performing various operations on the tables in the database, which may include a very time-consuming JOIN operation, which may require that all objects of all tables included in the JOIN be retrieved in order to determine which objects satisfy certain common attributes. For example, a query such as “Find all objects of Type A which contain in their hierarchy an object of type B with a certain value,” for example, “Find all ‘contracts’ that have ‘parties’ with name ‘SAP’” may be slow to process using conventional techniques because the conventional techniques may include the following steps: A) find all objects of Type B with the value; and B) navigate the hierarchy of B to get to A.

A typical example user may spend 10% of his/her computing time in storing information, and 90% of his/her computing time in retrieving information from previously stored information. Thus, it may be desirable to provide storage and retrieval techniques which improve the efficiency and speed of retrieval of information.

SUMMARY

According to one general aspect, a method includes generating a first address string representing a first relational path associated with a first database query retrieval of a first object included in a database. The method further includes storing the first address string in association with the first object.

According to another aspect, a method includes receiving a query requesting information associated with an entity related to one or more objects included in a database. The method further includes retrieving a first address string based on a search of address strings to determine address strings that indicate the entity, the first address string representing a first relational path associated with a first database query retrieval of a first object. The method further includes retrieving the first object based on the retrieved first address string.

According to another aspect, a method is provided for querying relational information associated with a first data object stored in a relational database. The method includes generating a plurality of relational strings representing a plurality of relationships between the first data object and one or more other data objects also stored in association with the relational database. The method further includes storing the plurality of the relational strings in association with the first object, and in response to a query related to the relational information between the first data object and at least one of the one or more other data objects, searching the stored plurality of the relational strings to retrieve results of the query.

According to yet another aspect, a system includes an address string generator configured to generate a first address string representing a first relational path associated with a first database query retrieval of a first object included in a database. The system further includes a storage engine configured to store the first address string in association with the first object.

According to yet another aspect, a computer program product is tangibly embodied on a computer-readable medium and is configured to cause a data processing apparatus to generate a first address string representing a first relational path associated with a first database query retrieval of a first object included in a database, and store the first address string in association with the first object.

DETAILED DESCRIPTION

FIG. 1is a block diagram of a system100for generating and processing address strings. In the example ofFIG. 1, an address string processing engine102includes various processing engines that provide and process address strings that may be stored in association with objects, for example, objects associated with databases, for example, objects associated with an object database104. For example, the object database104may include a relational database. The address strings may then be retrieved in response to a query or request for information, and a response to the query or request may be advantageously determined based on parsing the address strings to determine relational paths associated with retrieval of objects, instead of stepping through a relational path by loading objects at each step of the path. Thus, for example, navigating a hierarchy of objects associated with a database may include parsing the stored address strings, without a need to load objects and step up an object tree one object at a time. Although the following description refers primarily to the address string processing engine102as an example implementation, it should be understood that such address string processing engines may refer to any type of address string processing engine that generates and stores address strings associated with objects, and determines responses to requests for information associated with the objects based on retrieving and parsing the address strings.

InFIG. 1, the address string processing engine102is illustrated as including a query handler106that may receive, for example, a query or a request associated with a database. The query or request may, for example, be received by the query handler106from a user via a user interface108. The query or request may include, for example, a request to add a new object to the object database104, or it may include a request to update an existing object associated with the object database104. The query or request may include a request for information associated with one or more objects associated with the object database104. One skilled in the art of data processing will appreciate that there may be many different types of queries or requests for which a response may be determined based on storing and/or accessing objects associated with the object database104.

If the query or request, for example, indicates a request to add a new object to the object database104, the query handler106may generate the object and its unique identifier based on information associated with the query or request. In accordance with an example embodiment, an object address processor110may determine a location for storing the object, for example, in a table located in an object storage area112included in the object database104. The determination of the location may be based on a determination of one or more relationships between the object and other entities included in the object database104. For example, an example containment relationship for two example objects A and B may be defined such that A “contains” B if A is related to B, and if A is deleted then B is also deleted. For example, there may exist a containment relationship between an example object representing a student “Tom” and an example object representing a “Schedule” associated with the student “Tom” if it is true that deletion of the object representing the student “Tom” leads to deletion of the object representing the “Schedule” associated with the student “Tom.”

Further, an example reference relationship for two example objects A and B may be defined such that A “refers” to B if A is related to B but A may be deleted without impacting B. For example, the example object representing the student “Tom” may include a reference relationship with an example course object representing a course for which “Tom” is enrolled. Moreover, an index relationship may exist for entities included in a list. For example, “C[5]” may indicate the fifth course for which “Tom” may be enrolled, out of at least five courses.

An example type relationship may exist, between an object and a type associated with the object. For example, the example object representing the student “Tom” may include an object type relationship with an example object type “Student.”

After the object address processor110determines the location or direct address for storing the object based on the determination of the relationships, a storage engine114included in the address string processing engine102may then store the object at the location determined by the object address processor110, for example, in the object storage area112.

The address string processing engine102includes an address string generator116that may receive relational path information based on the determination of the relationships. The address string generator116may then generate one or more address strings representing relational paths associated with a database query retrieval of each object. The address strings may, for example, include human readable address strings representing the database relationships among the objects and other entities associated with the database, which may include navigation paths associated with navigating object trees for retrieving the objects based on database queries. The generated address strings for each object may then be stored by the storage engine114in an address string storage area116included in the object database104. According to an example embodiment, an indicator of the location of the stored object, such as the unique identifier or an address, may also be stored in the address storage area116, in association with the generated address strings.

According to an example embodiment, an example object may be assigned a human readable name. Further, an example object type, or ObjectType, may be assigned a human readable name. Thus, an object may be identified by a tuple including an “ObjectTypeName:ObjectName” format. According to an example embodiment, an example character or token such as “:” may be used to separate an ObjectType from an ObjectTypeName in an example address string. For example, as discussed above, a format “ObjectType:ObjectTypeName” may be used to represent an address of an object. Thus, an example string address “ObjectType1:Object1” may represent an address of an object named Object1 that is of type ObjectType1.

According to an example embodiment, an example character or token such as “.” may be used to separate address string elements, and to indicate a containment relationship. Thus, an example string address “ObjectType1:Object1.OT2:Object2” may represent an address of Object2, and may indicate the Object2 is of type OT2, and is contained in an object named Object1 that is of type ObjectType1. Thus, ObjectType1:Object1 is related to OT2:Object2, and deletion of ObjectType1 Object1 will lead to a deletion of OT2:Object2.

According to an example embodiment, a token or symbol such as “→” may be used to separate address string elements, and to indicate a reference relationship. For example, an example string address “ObjectType1:Object1.OT2:Object2→OT3:Object3” may represent an address of Object3, and may indicate that the Object2 discussed above refers to an Object3 of type O3. Thus, ObjectType1:Object1.OT2:Object2 is related to OT3:Object3 but the object addressed by ObjectType1:Object1.OT2:Object2 may be deleted from storage without impacting OT3:Object3.

According to an example embodiment, an example token or symbol such as “[N]” may be placed after a string element to indicate a position in a list containment or reference relationship, wherein N may include, for example, a number. For example, an example string address “ObjectType1 Object1.OT2[N]:Object2” may represent an address of Object2, and may indicate that Object1 of type ObjectType1 contains Object2 of type OT2 at the “Nth” position in a list containment relationship.

Thus, according to an example embodiment, string addresses associated with an object may be generated in accordance with an example format as follows: ObjectTypeName1:ObjectName1.ObjectTypeName2:ObjectName2→ObjectTypeName3[2]:ObjectName3→ObjectTypeName4:ObjectName4 . . . ObjectTypeNameN:ObjectNameN

The example format shown above may represent an object ObjectNameN of type ObjectTypeNameN on a relational path that includes an object ObjectName4 of type ObjectTypeName4 that is referenced by an object ObjectName3 having a type that is a second type in a list of types ObjectTypeName3. The ObjectName3 may be referenced by an object ObjectName2 of type ObjectTypeName2 that is contained in an object ObjectName1 of type ObjectTypeName1.

According to an example embodiment, each object may be addressed via more than one string address; however, each string address may identify only one object. Therefore, there may exist multiple navigation paths to one object as discussed further below. One skilled in the art of data processing will appreciate that example techniques discussed herein may also apply to other types of relationships, and are not limited only to the relationships discussed above. The example techniques discussed herein may generally relate to an example generic “human readable” string addressing mechanism for objects in a software application so that each address identifies an object. However, one skilled in the art of data processing will also appreciate that these example techniques may also apply to strings that are not easily read by humans as well.

If the query or request received by the query handler106, for example, indicates a query requesting information associated with the object database104, the query handler106may determine a search based on address strings retrieved by a retrieval engine118from the address string storage area116associated with their associated objects stored in the object storage area112. An address string parser120may then parse the retrieved strings to determine the relationships indicated by the address strings and the addresses of objects to be retrieved from the object storage area112by the retrieval engine118. According to an example embodiment, the desired objects may be retrieved based on the associated indicators of the locations of the stored objects. In accordance with an example embodiment, the query handler106may then generate a response to the query or request based on the relationships and/or the retrieved objects.

FIG. 2depicts an example schema illustrating example relationships among multiple example academic entities according to an example embodiment. In the example ofFIG. 2, a containment relationship is depicted by a directed solid line connecting the related entities, and a reference relationship is depicted by a directed dashed line. As shown inFIG. 2, a student St1202belonging to a school S1204has a schedule Sc1206. The student St1202takes multiple courses, including a fifth course C[5]208which is taught by a teacher T1210.

Using the example schema ofFIG. 2and the example string address generation techniques discussed previously, a string address for the student St1202may be generated as “School:S1.Student:St1” to provide a human-readable address. Similarly, a string address for the schedule Sc1206may be generated as “School:S1.Student:St1.Schedule:Sc1” to provide a human-readable address. A string address for the teacher T1210may be generated as “School:S1.Student:St1→Course:C[5]→Teacher:T1” to provide a human-readable address.

As another example, a second student, for example, student St2may belong to the school S1204, and may take a course C2, which may also be taught by the teacher T1210. Thus, another string address for the teacher T1210may be generated as “School:S1.Student:St2→Course:C2→Teacher:T1” to provide another human-readable address. Thus, the different string addresses for the teacher T1210illustrate two different navigation paths through an object hierarchy from the School S1204to the teacher T1210. In response to a query, for example, requesting all students enrolled in courses taught by the teacher T1210, all such string addresses associated with the object associated with the teacher T1210may be retrieved, for example, by the retrieval engine118from address string storage116, parsed by the address string parser120to determine the relational path, and processed by the query handler106to determine a response to the query. The string operations may significantly reduce retrieval time by reducing the amount of time spent in retrieving all objects at each level of an object hierarchy by relying on string operations instead.

An example query such as “Find all objects of Type A which contain in their hierarchy an object of type B with a certain value,” for example, “Find all ‘contracts’ that have ‘parties’ with name ‘SAP’” may be slow to process using conventional techniques because the conventional techniques may include the following steps:

A) find all objects of Type B with the value

B) navigate the hierarchy of B to get to A.

By using an example generic addressing mechanism as discussed herein it may be possible to issue a query such as “find all objects with a string address of the form: OtA:*.OtB:* with a certain value.” Retrieval of objects of Type A may thus be performed via a one step process that may not require conventional programmatic hierarchical navigation or object loading.

FIG. 3is a flowchart illustrating an example operation of the system ofFIG. 1. At302, a first address string representing a first relational path associated with a first database query retrieval of a first object included in a database may be generated. For example, the address string “School:S1.Student:St1→Course:C[5]→Teacher:T1” as discussed previously may be generated by the example address string generator116. The example address string represents a relational path through the school S1204, the student St1202, the course C[5]208, and the teacher T1210, as discussed previously.

At304, the first address string may be stored in association with the first object. For example, the example address string may be stored in the address string storage area116by the storage engine114as discussed previously. The example address string may be stored in association with the corresponding object stored in the object storage area112, such as the object representing the teacher T1210. For example, if all address strings are stored in association with their corresponding objects, then determinations of responses to queries may advantageously be performed more quickly and efficiently by performing operations on strings rather than by loading objects and programmatically navigating an object hierarchy.

FIG. 4is a flowchart illustrating an example operation of the system ofFIG. 1. At402, a query requesting information associated with an entity related to one or more objects included in a database may be received. For example, a query may be received by the example query handler106.

At404, a first address string may be retrieved based on a search of address strings to determine address strings that indicate the entity, the first address string representing a first relational path associated with a database query retrieval of a first object. For example, the retrieval engine118may retrieve all address strings from the address string storage area116that are associated with a particular object, or that indicate a particular entity based on the query.

At406, the first object may be retrieved based on the retrieved first address string. For example, the first object may be retrieved by the retrieval engine118from the object storage area112based on a determination made by the query handler106that the first object needs to be retrieved based on operations performed on the first address string.

FIG. 5is a flowchart illustrating an example operation of the system ofFIG. 1. More particularly,FIG. 5is a flowchart illustrating an example operation for querying relational information associated with a first data object stored in a relational database. At502, a plurality of relational strings representing a plurality of relationships between the first data object and one or more other data objects also stored in association with the relational database may be generated. For example, the example address string “School:S1.Student:St1→Course:C[5]→Teacher:T1” as discussed previously may be generated by the example address string generator116. The example address string represents a plurality of relationships between the teacher T1210and one or more other data objects such as the school S1204, the student St1202, and the course C[5]208, as discussed previously. Further, the example address string “School:S1.Student:St2→Course:C2→Teacher:T1” as discussed previously may be generated by the example address string generator116. The example address string represents a plurality of relationships between the teacher T1210and one or more other data objects such as the school S1204, a student St2, and a course C2, as discussed previously

At504, the plurality of the relational strings may be stored in association with the first object. For example, the example address strings may be stored in the address string storage area116by the storage engine114as discussed previously. The example address strings may be stored in association with the corresponding object stored in the object storage area112, such as the object representing the teacher T1210.

At506, in response to a query related to the relational information between the first data object and at least one of the one or more other data objects, the stored plurality of the relational strings may be searched to retrieve results of the query. For example, a query may be received by the example query handler106. For example, the first object may be retrieved by the retrieval engine118from the object storage area112based on a determination made by the query handler106that the first object needs to be retrieved based on operations performed on the stored address strings.

FIG. 6illustrates example strings that may be stored in the string address storage area116and the object storage area112. For example, a string address604illustrating a student “Sam Smith” contained in a school “Stanford” is stored in association with an object606representing student “Sam Smith.” As another example, a string address608illustrating a schedule “Sc1” contained in a student “Sam Smith” contained in a school “Stanford” is stored in association with an object610representing schedule “Sc1.” As discussed previously, more than one address string may identify a particular object, but each address string may identify one and only one object. An example address string may indicate: a) a 1-1 or unordered 1-n containment relationship; b) a 1-1 or unordered 1-n reference relationship; and/or c) a position of a containment or referred relationship if there exists an ordered 1-n or m-n relationship.

According to an example embodiment based on human readable strings, a human may advantageously be provided with meaningful, human readable navigation paths to each object in a software application, whereas conventional addressing mechanisms may either provide non-meaningful unique identifiers or may not capture the complete position of an object in an object hierarchy.

Further, according to an example embodiment, for each object stored in an object repository, all possible means of access to the object either in a containment or a reference relationship may advantageously be stored, for example, via address strings.

Moreover, according to an example embodiment, navigation of the object tree may advantageously be performed via a string operation, rather than conventional operations that may include loading objects into memory and programmatically walking the object hierarchy.

For applications that use relational data, the example object addressing techniques discussed herein may advantageously improve retrieval performance generally. For example, if all address strings for each object are stored in the object database104, a lookup on the object may be performed much faster, for example, via operations on the strings. Further, as discussed previously, navigating a hierarchy of objects may also be achieved by parsing strings instead of loading objects and moving up an object tree one loaded object at a time.

It is possible that operations for creating objects, based on example techniques discussed herein, may execute slower than conventional techniques; however, this may be diminished by using example optimization techniques such as asynchronous calls. However, retrieval of object trees may become relatively fast. Thus, applications that are designed more for consumption of data may advantageously benefit from the example techniques discussed herein.