TEMPORAL BINDING FOR SEMANTIC QUERIES

• US 20120158771A1
• Filed: 12/16/2010
• Published: 06/21/2012
• Est. Priority Date: 12/16/2010
• Status: Active Grant

• Current Assignee: Microsoft Technology Licensing LLC (Microsoft Corporation)
• Original Assignee: Microsoft Corporation
• Inventors: Jackson, Thomas E., Bowers, Stuart, Campbell, David, Aust, Brian, Karkanias, Chris, Brown, Allen
• Granted Patent: US 8,407,242 B2
• Time in Patent Office: Days
• US Class Current: 707/769
• CPC Class Codes: G06F 16/2477 Temporal data queries

Abstract

Described are techniques to facilitate temporal features in a semantic data store. Information about lifetimes of facts in a semantic store is maintained. Even when a fact is logically deleted, a physical record is kept available. The record of a logically deleted or invalid fact has associated lifetime information. For example, valid-from and valid-to time values. The record of a fact not yet deleted may have a valid-from time value indicating when it was created, became valid, etc. Queries against the semantic store may specify a timeslice (a point in time or a time range). The lifetime information can be used to satisfy such time-specific queries. Because records are maintained after they are logically deleted, it is also possible to accurately query a past state of the semantic store. Even if such a query is run at different times, same results may be obtained.

Claims

1. A method performed by one or more computers, the method comprising:

executing a graph-store, the graph-store providing graph querying semantics to access facts stored in the graph-store, the graph-store including a first set of facts each of a first fact type;

in response to a first user update submitted to the graph-store that comprises values of a new given fact of the first time, adding the given fact and its values to the graph-store, automatically adding time information to the stored given fact that indicates a time of adding the given fact to the graph-store; and

in response to a second user update submitted to the graph-store that requests deletion of the given fact, automatically modifying the given fact in the graph-store to indicate that the given fact is no longer valid and to indicate a time of deleting the given fact.

2. A method according to claim 1, wherein the modifying comprises moving the fact from a first table to a second table, the first table including a valid-from column, the second table including a valid-from column and a valid-to column.

3. A method according to claim 2, wherein the modifying further comprises populating the moved given fact in the second table such that valid-to column contains the time of deleting the given fact.

4. A method according to claim 2, wherein the modifying further comprises physically deleting the given fact from the first table.

5. A method according to claim 1, wherein the graph-store uses a relational database to store the facts.

6. A method according to claim 1, further comprising receiving a query specifying a condition and a range of time, and executing the query by selecting facts from the graph-store that satisfy the condition and that have time information indicating that the facts where valid during the range of time.

7. A method according to claim 1, wherein regardless of when the query is executed the selecting will select facts that, based on the time information, were valid during the time range even if the facts were deleted after the time range.

8. One or more computer-readable storage media storing information that when processed by a computer causes the computer to perform a process, the process comprising:

maintaining a semantic data store that stores graphs comprised of interrelated facts of different fact types, each fact type comprising a subject data type, predicate data type, and object data type, each fact comprising a statement comprised of values of the data types of its fact type, respectively, wherein the semantic data store is configured to execute semantic queries; and

the maintaining including adding new facts and logically deleting existing facts, wherein each adding of a new fact comprises automatically adding to the new fact a valid-from time value indicating a time before which the new fact was invalid and after which the new fact was valid, and wherein each logically deleting an existing fact comprises adding a valid-to time value indicating a time before which the existing fact was valid and after which the existing fact became invalid.

9. One or more computer-readable storage media according to claim 8, wherein each logically deleted fact, having at one time been added, includes a valid-from time value corresponding to when it was added to the semantic data store.

10. One or more computer-readable storage media according to claim 9, wherein each fact that has not been logically deleted has no valid-to time value, whereby some facts are currently valid as indicated by their lack of a valid-to time value and some facts are currently invalid as indicated by their having a valid-to time value, such that over time the facts that are valid and invalid changes, some becoming invalid.

11. One or more computer-readable storage media according to claim 8, wherein a same query that specifies a time of facts to be retrieved, when run at different query times, returns a same set of facts that match the query and that have valid-from time values that precede the specified time and that have no valid-to time values that precede or match the specified time, wherein the same facts are in the returned set regardless of when the query time is executed including at a time when some of the facts in the set have been logically deleted.

12. One or more computer-readable storage media according to claim 8, wherein the semantic data store stores currently valid facts in a first table and stores currently invalid facts with valid-to time values in a second table.

13. One or more computer-readable storage media according to claim 12, wherein when a fact is logically deleted it is automatically removed from the first table and automatically added to the second table and a corresponding valid-to time value is added to the logically deleted fact, the logically deleted fact including a same valid-from time value that it had when it was stored in the first table.

14. One or more computer-readable storage media according to claim 13, wherein the first table has a valid-from column that stores the valid-from time value of the logically deleted fact, and wherein the second table has a valid-from column that stores the valid-from time value of the logically deleted record and has a valid-to column that stores the valid-to time value of the logically deleted record.

15. One or more computer-readable storage media according to claim 14, wherein the process further comprises receiving, after the logically deleted fact was logically deleted, a query specifying a time range of facts to the retrieved, wherein the logically deleted fact is included in a result of the received query based on the valid-from time value of the logically deleted fact falling within the time range and the valid-to time value falling outside the time range.

16. A computer comprising storage and a processor, the storage storing:

a graph store storing a graph of facts, the facts conforming to a schema describing the graph, wherein each fact comprises a triplet comprising a subject value, a predicate value, and an object value, wherein the facts are instances of varying different fact types that have different subject data types and/or different predicate data types and/or different object data types, and wherein the semantic graph store is configured to receive semantic queries for facts in the graph store, wherein when facts are stored by automatically maintaining information indicating lifespans of each fact in the graph store.

17. A computer according to claim 16, wherein when a query is executed at a given time and specifies a timeslice earlier that precedes the given time, facts that match the query and that have lifespans that correspond to the timeslice are returned as satisfying the query, even though some of the returned facts have lifespans ending prior to the given time.

18. A computer according to claim 16, wherein the facts are stored in tables in a relational database, wherein tables represent predicates associated with corresponding fact types.

19. A computer according to claim 16, wherein a parameterized view is used to view facts at any point in time according to the lifespans.

20. A computer according to claim 16, wherein the graph store receives graph queries having graph semantics and form, and converts the queries into relational database queries to be executed against a relational database storing the facts.