Patent US6026413A successfully refreshed from Google Patents.
US6026413A
Expired / Lapsed
US
⏱️ 0.0 years remaining
Determining how changes to underlying data affect cached objects
Assignee: International Business Machines Corp
•
Filing: 1997-08-01
•
Granted: 2000-02-15
•
Expires: 2017-08-01
Abstract
Abstract A determination can be made of how changes to underlying data affect the value of objects. Examples of applications include: caching dynamic Web pages; client-server applications whereby a server sending objects (which are changing all the time) to multiple clients can track which versions are sent to which clients and how obsolete the versions are; and any situation where it is necessary to maintain and uniquely identify several versions of objects, update obsolete objects, quantitatively assess how different two versions of the same object are, and/or maintain consistency among a set of objects. A directed graph, called an object dependence graph, may be used to represent the data dependencies between objects. Another aspect is constructing and maintaining objects to associate changes in remote data with cached objects. If data in a remote data source changes, database change notifications are used to "trigger" a dynamic rebuild of associated objects. Thus, obsolete objects can be dynamically replaced with fresh objects. The objects can be complex objects, such as dynamic Web pages or compound-complex objects, and the data can be underlying data in a database. The update can include either: storing a new version of the object in the cache; or deleting an object from the cache. Caches on multiple servers can also be synchronized with the data in a single common database. Updated information, whether new pages or delete orders, can be broadcast to a set of server nodes, permitting many systems to simultaneously benefit from the advantages of prefetching and providing a high degree of scaleability.
Inventors
- 👤 James Robert Harold Challenger
- 👤 Paul Michael Dantzig
- 👤 Arun K. Iyengar
- 👤 Gerald A. Spivak
Bibliographic Details
Application Number
—
Jurisdiction
US
Data Source
google_patents
Last Synchronized
2026-10-30 17:03
CPC Classifications
G; G06; G06F; G06F15/00; G06F12/00; G06F12/02; G06F12/08; G06F12/0802; G06F12/0806; G06F12/0815; G06F16/00; G06F16/90; G06F16/95; G06F16/957; G06F16/9574; Y; Y10; Y10S; Y10S707/00; Y10S707/912; Y10S707/922; Y10S707/951; Y10S707/99941; Y10S707/99944; Y10S707/99945; Y10S707/99951; Y10S707/99952; Y10S707/99953
Claims Analysis
Total Claims: 66
Claim 1
Independent Claim
118 words
In a computer system having one or more caches storing one or more complex objects, a method for determining how changes to underlying data can affect values of one or more complex objects, comprising the steps of: identifying at least part of the underlying data, wherein the underlying data may or may not be cachable; mapping said at least part of the underlying data to one or more of said complex objects having one or more data dependencies on said at least part of the underlying data; and maintaining an object dependence graph (G) which may change over time and which includes a plurality of graph objects and edges indicating one or more data dependencies between graph objects.
Claim 2
Dependent Claim
118 words
In a computer system having one or more caches storing one or more complex objects, a method for determining how changes to underlying data can affect values of one or more complex objects, comprising the steps of: identifying at least part of the underlying data, wherein the underlying data may or may not be cachable; mapping said at least part of the underlying data to one or more of said complex objects having one or more data dependencies on said at least part of the underlying data; and maintaining an object dependence graph (G) which may change over time and which includes a plurality of graph objects and edges indicating one or more data dependencies between graph objects.
Claim 3
Dependent Claim
35 words
The method of claim 1 further comprising a plurality of computers wherein a first set of computers associated with a first cache is disjoint from a second set of computers associated with said mapping step.
Claim 4
Dependent Claim
29 words
The method of claim 1 wherein said mapping step, further comprises the step of a program scheduling operations where different schedules might result in different changes to underlying data.
Claim 5
Dependent Claim
17 words
The method of claim 3 wherein said program scheduling operations is a compiler, run-time system, or database.
Claim 6
Dependent Claim
30 words
The method of claim 1 in which said mapping step comprises: using said graph to map said at least part of the underlying data to at least one complex object.
Claim 7
Dependent Claim
26 words
The method of claim 1, further comprising the step of assigning weights to the edges wherein the weights are correlated with an importance of data dependencies.
Claim 8
Dependent Claim
20 words
The method of claim 6 wherein a weight of at least one edge does not change after it is assigned.
Claim 9
Dependent Claim
162 words
The method of claim 6, wherein: (1) two versions o1 -- v1 and o1 -- v2 of a graph object o1 exist; and (2) the object dependence graph G contains at least one edge (o2, o1) terminating in o1 and having an assigned weight; further comprising the steps of: for one or more edges (o2, o1) terminating in said o1 and comprising a set S, maintaining a version number of said object (s) o2 which is consistent with o1 -- v1 and a second version number of said object (s) o2 which is consistent with o1 -- v2; determining how similar o1 -- v1 and o1 -- v2 are based on a sum of the weights of edges (o2, o1) in said set S such that a same version of said graph object o2 is consistent with said versions o1 -- v1 and o1 -- v2 and a sum of the weights of all edges terminating in o1 in said set S.
Claim 10
Dependent Claim
73 words
The method of claim 8 wherein said step of determining how similar said two versions are, further comprises the step of dividing said sum of the weights of edges (o2, o1) in said set S such that a same version of said graph object o2 is consistent with said versions o1 -- v1 and o1 -- v2 by said sum of the weights of all edges terminating in o1 in said set S.
Claim 11
Dependent Claim
53 words
The method of claim 1, wherein said mapping farther comprises the step of: using information about how one or more complex objects would be affected by changes to said at least part of the underlying data to determine whether or how to make changes to said at least part of the underlying data.
Claim 12
Dependent Claim
37 words
The method of claim 1, wherein a program implementing said mapping step generates one or more of: multiple processes; multiple threads; and one or more long-running processes or threads managing storage for said one or more caches.
Claim 13
Dependent Claim
60 words
The method of claim 11, wherein a program implementing said mapping step generates at least one long-running process, further comprising the steps of: an application program identifying a change to at least part of the underlying data; and the application program communicating an identified change to at least part of the underlying data to said program implementing said mapping step.
Claim 14
Dependent Claim
51 words
The method of claim 1 wherein said mapping further comprises the step of: identifying a change to said at least part of the underlying data; and identifying how one or more complex objects are affected, in response to said identifying a change to said at least part of the underlying data.
Claim 15
Dependent Claim
125 words
The method of claim 13, wherein said at least part of the underlying data is stored in one or more remote data sources, further comprising the steps of: communicating to a cache, one or more of: information about at least part of said underlying data which has changed; and information which includes the identity of at least one object whose value has changed as the result of said underlying data which has changed; and information which allows the identity to be determined of at least one object whose value has changed as the result of said underlying data which has changed; and removing an object from the cache, or updating a new version of an object in the cache, in response to said communicating step.
Claim 16
Dependent Claim
40 words
The method of claim 1 further comprising the step of determining that a version of a complex object stored in a cache would become highly obsolete as a result of changes to said at least part of the underlying data.
Claim 17
Dependent Claim
21 words
The method of claim 15 further comprising the step of deleting a highly obsolete version of an object from the cache.
Claim 18
Dependent Claim
22 words
The method of claim 15 wherein the version of an object is considered to be highly obsolete whenever it is not current.
Claim 19
Dependent Claim
92 words
The method of claim 15 wherein said determining that a version of an object (o1 -- v1) would become highly obsolete comprises the steps of: maintaining an object dependence graph (G) which may change over time and which includes a plurality of graph objects (o1 . . . on) and edges indicating one or more data dependencies between graph objects; and determining that said o1 -- v1 would become highly obsolete based on a number of edges (o2, o1) such that o1 -- v1 is inconsistent with a current version of o2.
Claim 20
Dependent Claim
23 words
The method of claim 15, further comprising the step of replacing a highly obsolete version of the object with a more recent version.
Claim 21
Dependent Claim
17 words
The method of claim 19 wherein the more recent version is a current version of the object.
Claim 22
Dependent Claim
151 words
The method of claim 15 where in said step of determining that a version o1 -- v1 of an object o1 stored in a cache would become highly obsolete, comprises the steps of: maintaining an object dependence graph (G) which may change over time and which includes a plurality of graph objects and edges indicating one or more data dependencies between graph objects; initializing and maintaining weight -- act fields for said o1 -- v1 corresponding to one or more edges terminating in said o1; for one or more changes to a current version of a graph object o2 such that an edge from said object o2 to said object o1 exists such that o1 -- v1 has a weight -- act field, decrementing the weight -- act field corresponding to the edge; and determining if said o1 -- v1 would become highly obsolete based on its weight -- act fields.
Claim 23
Dependent Claim
60 words
The method of claim 21, further comprising the steps of: maintaining a threshold weight for said o1 -- v1; wherein said determining if said o1 -- v1 would become highly obsolete based on its weight -- act fields includes the step of comparing a sum of the weight -- act fields for said o1 -- v1 to said threshold weight.
Claim 24
Dependent Claim
58 words
The method of claim 21, further comprising the steps of: assigning weights to the edges of the object dependence graph wherein the weights are correlated with an importance of data dependencies; and initializing one or more weight -- act fields for said o1 -- v1 to one or more weights of corresponding edges in the object dependence graph.
Claim 25
Dependent Claim
54 words
The method of claim 21, further comprising the step of setting the weight -- act field corresponding to an edge from said o2 to said o1 in the object dependence graph, that is greater than a predetermined minimum possible value, to said predetermined minimum possible value whenever the current version of o2 is updated.
Claim 26
Dependent Claim
52 words
The method of claim 15 where the step of determining that a version of a complex object o1 stored in a cache would become highly obsolete comprises the step of determining a number of edges (o2, o1) such that said version of o1 is inconsistent with the current version of said o2.
Claim 27
Dependent Claim
39 words
The method of claim 25 wherein said stop of determining that a version of a complex object o1 stored in a cache would become highly obsolete further is based on the total number of edges terminating in said o1.
Claim 28
Dependent Claim
29 words
The method of claim 1 wherein said one or more caches includes one or more of: a multiple version cache; a single version cache; and a current version cache.
Claim 29
Dependent Claim
55 words
The method of claim 27 wherein said one or more caches includes at least one single version cache c1, further comprising the step of: for at least one of the objects o1, maintaining a consistency set of other objects o2 such that o1 and o2 must be consistent whenever they are both contained in c1.
Claim 30
Dependent Claim
30 words
The method of claim 28 further comprising the step of ensuring that if said o1 and said o2 are both in c1, then said o1 and said o2 are consistent.
Claim 31
Dependent Claim
45 words
The method of claim 28, further comprising the step of: using the consistency set for an object o1 to decide whether or not to add a version of the object o1 to the single version cache, possibly replacing a previous version of the object o1.
Claim 32
Dependent Claim
134 words
The method of claim 29 further comprising the steps of: for multiple objects o1, . . . , on in a single version cache c1; replacing each object oi with a different version in c1 without ensuring that all constraints imposed by a consistency set for the object oi are satisfied at the time said oi is updated but instead adding objects obj1 from a consistency set for said oi for which an inconsistent version of obj1 might exist in c1 to a consistency stack; after all objects o1, . . . , on in c1 have been replaced with current versions, traversing all objects on the consistency stack and for each such object obj1 for which an inconsistent version exists in c1, removing it from c1 or replacing it with a consistent version.
Claim 33
Dependent Claim
24 words
The method of claim 31 further comprising the step of implementing the consistency stack by storing references to said objects on a linked list.
Claim 34
Dependent Claim
54 words
The method of claim 31 further comprising the steps of: using one or more balanced trees for implementing said consistency stack; and for at least one object obj1, verifying that a reference to said obj1 is not already included on the consistency stack before adding a reference to said obj1 to the consistency stack.
Claim 35
Dependent Claim
152 words
The method of claim 29 further comprising the steps of: adding a current version of said object o1 to the single version cache, possibly replacing a previous version of the object o1; identifying one or more objects o2 in the consistency set for o1 such that a noncurrent version o2 -- v of said object (s) o2 is contained in said cache c1 and said o2 -- v was created before the current version of said o1 was created; removing said o2 -- v from said cache c1 or replacing o2 -- v with a more recent version of said object (s) o2; recursively applying to objects in the consistency set for said object (s) o2, said step of identifying one or more objects and said step of removing said o2 -- v from said cache c1 or replacing o2 -- v with a more recent version of said object (s) .
Claim 36
Dependent Claim
18 words
The method of claim 29 wherein said consistency set (s) are implemented using one or more linked lists.
Claim 37
Dependent Claim
18 words
The method of claim 1 wherein said G is one of: a simple dependence graph; and a multigraph.
Claim 38
Dependent Claim
32 words
The method of claim 36 wherein said G is a simple dependence graph in which proper maximal nodes are complex objects and proper leaf nodes are underlying data which are not objects.
Claim 39
Dependent Claim
43 words
The method of claim 37 wherein said maintaining an object dependence graph comprises the steps of: maintaining an outgoing adjacency list for at least one proper leaf node v; and maintaining an incoming adjacency list for at least one proper maximal node w.
Claim 40
Dependent Claim
24 words
The method of claim 38, further comprising the step of accessing one of outgoing adjacency lists and incoming adjacency lists via a hash table.
Claim 41
Dependent Claim
61 words
The method of claim 38 wherein said maintaining an object dependence graph further comprises the steps of: when initially changed data includes some data d which could be represented by a proper leaf node changes, searching for the outgoing adjacency list corresponding to d. if the outgoing adjacency list is found, examining the list to determine which complex objects are affected.
Claim 42
Dependent Claim
23 words
The method of claim 38, further comprising the step of deleting at least one proper maximal node w from the object dependence graph.
Claim 43
Dependent Claim
57 words
The method of claim 41 wherein said step of deleting at least one proper maximal node w from the object dependence graph further comprises the steps of: deleting said w from the outgoing adjacency list for at least one proper leaf node on the incoming adjacency list for w; deleting the incoming adjacency list for said w.
Claim 44
Dependent Claim
23 words
The method of claim 39, further comprising the step of deleting at least one proper leaf node v from the object dependence graph.
Claim 45
Dependent Claim
56 words
The method of claim 43 wherein said step of deleting at least one proper leaf node v from the object dependence graph, further comprises the steps of: deleting v from the incoming adjacency list for one or more proper maximal nodes on the outgoing adjacency list for v; deleting the outgoing adjacency list for said v.
Claim 46
Dependent Claim
111 words
The method of claim 1 wherein a graph object r is a relational object (RO) which has an associated relational specifier which can represent one of single (SRO) or multiple (MRO) records and wherein said maintaining an object dependence graph further comprises the steps of: (a) storing the relational specifier for said r; (b) if one or more graph objects include said r, adding one or more dependencies from said r to one or more graph objects which include said r; and (c) if said r includes one or more graph objects, adding one or more dependencies to said r from said one or more graph objects included by said r.
Claim 47
Dependent Claim
84 words
The method of claim 45, further comprising the steps of: assigning weights to the edges wherein the weights are correlated with an importance of data dependencies; and wherein one of said steps (b) and (c) include the step of determining the weight of at least one of the dependencies corresponding to an RO node r1 containing an RO node r2, according to one or both of: a percentage of records of said r1 contained by said r2; and a relative importance of said records.
Claim 48
Dependent Claim
137 words
The method of claim 45 further comprising one or both of the steps of: (d) adding one or more dependencies from said r to another RO r2 wherein said another RO r2 does not include said r using a metric based on one or both of: a percentage of records in said r which are also contained in said r2; and a relative importance of the records in said r which are also contained in said r2; (e) adding one or more dependencies from another RO r3 to r wherein said r does not include said r3 using a metric based on one or both of: a percentage of records in said r3 which are also included in said r; and a relative importance of the records in said r3 which are also contained in said r.
Claim 49
Dependent Claim
49 words
The method of claim 47, further comprising the steps of: assigning weights to the edges wherein the weights are correlated with an importance of data dependencies; and calculating the weight of said one or more dependencies added in one or both of steps (d) and (e) using said metric.
Claim 50
Dependent Claim
27 words
The method of claim 45 wherein said r is one of: a newly created node; an existing node being modified; an SRO node; and an MRO node.
Claim 51
Dependent Claim
33 words
The method of claim 46 wherein one or more relational specifiers include relation names such that pairs of ROs having a common record have a high probability of possessing a same relation name.
Claim 52
Dependent Claim
27 words
The method of claim 50 further comprising the step of segregating ROs using one of: relation names; and a balanced tree in conjunction with the relation names.
Claim 53
Dependent Claim
47 words
The method of claim 45 wherein said step of identifying at least part of the underlying data comprises the steps of: identifying a relational specifier; and locating one or more ROs in the object dependence graph having one or more records in common with the relational specifier.
Claim 54
Dependent Claim
58 words
The method of claim 1, wherein said mapping comprises the steps of: visiting a set of one or more nodes (update -- set) in the object dependence graph corresponding to said at least part of the underlying data; and traversing the edges in the object dependence graph in order to visit nodes reachable from said update -- set.
Claim 55
Dependent Claim
27 words
The method of claim 53 wherein said traversing comprises the step of traversing the object dependence graph in one of: a depth-first manner; and a breadth-first manner.
Claim 56
Dependent Claim
70 words
The method of claim 53 further comprising the steps of: maintaining a timestamp which uniquely identifies each object dependence graph traversal; storing the timestamp at a vertex of the object dependence graph whenever the vertex is visited for the first time during a traversal; and determining whether a vertex has been visited during the current traversal by comparing the timestamp at the vertex to the timestamp for the current traversal.
Claim 57
Dependent Claim
19 words
The method of claim 55, further comprising the step of incrementing the time stamp for each new graph traversal.
Claim 58
Dependent Claim
149 words
The method of claim 1, wherein two versions o1 -- v1 and o1 -- v2 of a graph object o1 exist, and the object dependence graph G contains at least one edge (o2, o1) terminating in o1, further comprising the steps of: for one or more edges (o2, o1) terminating in said o1 and comprising a set S, maintaining a version number of said object (s) o2 which is consistent with o1 -- v1 and a second version number of said object (s) o2 which is consistent with o1 -- v2; determining how similar o1 -- v1 and o1 -- v2 are based on a number of edges (o2, o1) in said set S such that a same version of a graph object o2 is consistent with said versions o1 -- v1 and o1 -- v2 and a number of all edges terminating in o1 in said set S.
Claim 59
Dependent Claim
71 words
The method of claim 57 in which said step of determining how similar o1 -- v1 and o1 -- v2 are, comprises the step of dividing a number of edges (o2, o1) in said set S such that a same version of a graph object o2 is consistent with said versions o1 -- v1 and o1 -- v2 by a number of all edges terminating in o1 in said set S.
Claim 60
Dependent Claim
31 words
The method of claim 1 in which at least some of the objects are Web documents and at least some of the underlying data are part of one or more databases.
Claim 61
Dependent Claim
75 words
The method of claim 1, further comprising the step of using information on how a set s -- update of one or more graph objects would be affected by changes to the underlying data, in conjunction with the object dependence graph to determine how at least one other graph object having dependencies, specified either directly or transitively by the object dependence graph, on one or more objects in said s -- update would be affected.
Claim 62
Dependent Claim
182 words
In a computer system including one or more caches storing one or more complex objects, and one or more remote data sources storing underlying data which may affect a current value of one or more of said objects, a method comprising the steps of: maintaining an object dependence graph which may change over time and which includes a plurality of graph objects and edges indicating one or more data dependencies between said graph objects, recognizing when at least part of said underlying data has changed; communicating to a cache, one or more of: information about at least part of said underlying data which has changed; and information which includes the identity of at least one object whose value has changed as the result of said underlying data which has changed; and information which allows the identity to be determined of at least one object whose value has changed as the result of said underlying data which has changed; and removing an object from the cache, or updating a new version of an object in the cache, in response to said communicating step.
Claim 63
Dependent Claim
182 words
In a computer system including one or more caches storing one or more complex objects, and one or more remote data sources storing underlying data which may affect a current value of one or more of said objects, a method comprising the steps of: maintaining an object dependence graph which may change over time and which includes a plurality of graph objects and edges indicating one or more data dependencies between said graph objects, recognizing when at least part of said underlying data has changed; communicating to a cache, one or more of: information about at least part of said underlying data which has changed; and information which includes the identity of at least one object whose value has changed as the result of said underlying data which has changed; and information which allows the identity to be determined of at least one object whose value has changed as the result of said underlying data which has changed; and removing an object from the cache, or updating a new version of an object in the cache, in response to said communicating step.
Claim 64
Dependent Claim
54 words
A program storage device readable by a machine, tangibly embodying a program of instructions executable by the machine to perform method steps for determining how changes to underlying data can affect values of one or more complex objects, according to any of claims 1-2, 4-11, 13, 18, 21-24, 28-31, 34, 52, 53, or 55.
Claim 65
Dependent Claim
113 words
In a computer system having one or more caches storing one or more complex objects, a method for determining how changes to underlying data can affect values of one or more complex objects, comprising the steps of: identifying at least part of the underlying data, wherein the underlying data may or may not be cachable; and mapping said at least part of the underlying data to one or more of said complex objects having one or more data dependencies on said at least part of the underlying data, wherein at least some of the objects are Web documents and at least some of the underlying data are part of one or more databases.
Claim 66
Dependent Claim
113 words
In a computer system having one or more caches storing one or more complex objects, a method for determining how changes to underlying data can affect values of one or more complex objects, comprising the steps of: identifying at least part of the underlying data, wherein the underlying data may or may not be cachable; and mapping said at least part of the underlying data to one or more of said complex objects having one or more data dependencies on said at least part of the underlying data, wherein at least some of the objects are Web documents and at least some of the underlying data are part of one or more databases.
References Cited (Backward Citations)
US4325120A
Cited
US4322795A
Cited
US5058185A
Cited
US5317716A
Cited
EP0396834A1
Cited
US5226143A
Cited
US5410697A
Cited
US5261069A
Cited
US5357618A
Cited
US5355477A
Cited
US5287507A
Cited
US5396614A
Cited
US5434992A
Cited
EP0604013A2
Cited
US5560007A
Cited
US5544345A
Cited
US5546579A
Cited
US5574902A
Cited
US5542078A
Cited
US5713003A
Cited
US5689711A
Cited
US5881229A
Cited
EP0747840A1
Cited
US5778427A
Cited
WO1997015890A1
Cited
US5797004A
Cited
US5873084A
Cited
US5862325A
Cited
US5842216A
Cited
GB2317302A
Cited
US5787470A
Cited
US5852717A
Cited
USPTO Annuity & Maintenance Windows
| Annuity Stage | Window Opens | Payment Deadline | Surcharge Period Until | Estimated Fee | Status |
|---|---|---|---|---|---|
| 3.5 Years (Year 4) | 2003-02-14 | 2003-08-16 | 2004-02-15 | $2000.00 | Window Closed / Lapsed |
| 7.5 Years (Year 8) | 2007-02-14 | 2007-08-16 | 2008-02-15 | $3760.00 | Window Closed / Lapsed |
| 11.5 Years (Year 12) | 2011-02-14 | 2011-08-16 | 2012-02-15 | $7700.00 | Window Closed / Lapsed |