Data processing: database and file management or data structures – Database design – Data structure types
Reexamination Certificate
1999-11-12
2003-05-13
Robinson, Greta (Department: 2177)
Data processing: database and file management or data structures
Database design
Data structure types
C707S793000, C707S793000, C707S793000, C707S793000
Reexamination Certificate
active
06564218
ABSTRACT:
The present invention relates to a method of checking the validity of a set of digital information contained in cache means connected to an information source by comparing validity information associated with said set of digital information and validity information associated with corresponding digital information in said information source.
The invention also relates to a method of and an apparatus for retrieving digital information from an information source having cache means connected thereto.
Retrieving digital information from an information source, e.g. one or more databases, is widespread and already used by most companies deploying information technology equipment, e.g. in client-server systems connecting users to databases. Typically, the users request information regarding customers, products, logistics, economy or other subjects. Also the emerging e-trade solutions are based on customers client nodes connected to database servers via the Internet.
When a client retrieves data from an information source or remote databases the speed at which digital information or data are fetched is given by a number of parameters. Cached data that are located in close proximity to the client will be fetched fast because they do not have to travel a long way on a crowded network. Data that must be fetched from a remote database will have to be retrieved from the database disk and managed by the database server CPU. Thus the main parameters are distance, network bandwidth, database-server capability and database storage media access speed.
Client-server communication is often implemented in a not very optimal way as the software used is often designed for maximum functionality and flexibility, not necessarily optimum performance. Many tools will supply the requested information, yet at the same time consume substantial resources on the computers involved (CPU, network, etc.), e.g. many tools will start a new process to serve a user request.
The usual method in order to avoid requesting the same data twice is a cache. A cache is generally a temporary storage of information nearer to the point of use than the original location. For example, in a web system data files from the web server are typically cached on the client; e.g. a price list or a map showing the supplier's address. This is a standard feature of most HTML (HyperText Markup Language) browsers. The next time the client needs the information, it is accessed faster because it can be read from the cache, e.g located on the client hard disk or in RAM, instead of having to be transferred across the network, e.g. the Internet.
One of the important issues of caching is the fact that the information stored in cache, e.g. on a client, will not automatically be updated upon server updates. Therefore, prior to retrieval of digital information located in a cache memory, a validity check has to be performed in order to determine whether the cached digital information is outdated or not. An implementation is described in patent application WO 97/21177. This document describes the use of time stamps on cache data and on index data in the database in order to perform the validity check. The validity check is performed by comparing a time stamp associated with a respective cache database entry and a time stamp associated with the index to the corresponding data entry in the master database. This document also describes different data locking methods to deal with real time update of data that is accessed by many clients.
Notifying the client that previously fetched data have been changed can also be performed by tracking the information on the server and sending notification about updated data to the client. Such a method is described in U.S. Pat. No. 4,714,992: “Communication for version management in a distributed information service”. This patent describes a system with a updated master database and a replica database holding the same information as the master database. Only the master database is updated and valid at all times. When the replica database is going to be updated, the replica database sends a query to the master database for identifiers of obsolete records. This allows the replica database to redirect client queries for the obsolete data to the master database until the replica database has been updated.
The U.S. Pat. No. 5,842,216: “System for sending small positive data notification messages over a network to indicate that a recipient node should obtain a particular version of a particular data item” describes a system in which a small message is sent from the database server to the recipient notifying the recipient that data have been updated. The massage includes a time stamp, the data location and a check sum of the data held in that particular location. Based on the time stamp, the recipient can determine whether updated data should be fetched. Based on the location and the check sum, the recipient can look for the data in a local cache if a cache is available.
Version control at the query level is described in U.S. Pat. No. 5,892,914: “System for accessing distributed data cache at each network node to pass requests and data”. This patent describes a method of connecting multiple servers each storing a fraction of a total cache, a Network Distributed Cache. When a client needs information, the client sends a query to one of the cache servers, and the query and the data held in that particular server are passed on to another server for completion. If all the requested data are fetched, the data are sent to the client. Otherwise, the query and the data are sent to the next cache server. This method results in a large number of version numbers, because the data object (e.g. a browser request from the client to the application server) is identified by all the parameters included in the request.
Considering a scenario where a query for products is made for a certain country, product group and date, the cache on the application server will have to contain data for all combinations of these parameters, a phenomenon that is known as tile Cartesian product. For 50 countries, 100 product categories and 100 dates the cache would contain 50*100*100=500,000 entries. Generally, N parameters and M values per parameter result in M
N
cache entries. This problem is inherent to all methods which identify a query result using a single version number.
Version control at the database level, as described in U.S. Pat. No. 5,893,117: “Time-stamped database transaction and version management system”, deals with storing many versions of the same data entry, giving each entry a time stamp and building a data structure that allows the clients to track any version of a given data entry. The described system facilitates version control in a data base environment that is updated simultaneously by many users, e.g. software development projects where a number of developers write new codes for the same program. As a result, a large number of objects (records) has to be tracked For similar requests, e.g. querying a product price for different categories and different dates in the same country, the update status would have to be queried for every category and date.
Further, application specific programs have been developed, optimizing requests by caching data in program memory. This approach has two disadvantages: it requires the application program to be present on the client (and therefore application specific codes to be loaded, as an applet, through the network) and it increases program complexity and thus development time.
An object of the present invention is to provide a method of checking the validity of a set of digital information contained in cache means connected to an information source, as described in the introductory part in claim 1, which enables a more rapid and less memory requiring validity check compared to known methods.
According to the invention the object is achieved by a method of the above-mentioned type which is characterized by
specifying two or more overlapping supersets of information having said set of digit
Altera Law Group LLC
Black Linh
Premitech ApS
Robinson Greta
LandOfFree
Method of checking the validity of a set of digital... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method of checking the validity of a set of digital..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method of checking the validity of a set of digital... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3075950