Caching optimization with disk and/or memory cache management

Details Caching optimization with disk and/or memory cache management Caching optimization with disk and/or memory cache management

1998-10-05

2001-12-04

Alam, Hosain T. (Department: 2172)

Data processing: database and file management or data structures

Database design

Data structure types

C707S793000, C706S045000

Reexamination Certificate

active

06327587

ABSTRACT:

BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention relates to database, data warehouse, and data mart technology and, more particularly, to an improved system and method for exploring information relationships in data.
2. Discussion of Related Art
Modern computing databases have extremely large quantities of data. Businesses often desire to discover information relationships in this data to make better informed business decisions. In this regard, “data warehousing” is used to describe computing technologies used to discover relationships within a database, and “data mart” is used to describe technologies for a subject-specific data warehouse.
To date, data warehousing and data mart tools have been undesirable because of their high cost, both in infrastructure and human capital. Modern systems are effectively customized database applications. Consequently, exploring relationships usually involves the creation of new, custom queries and typically requires a management information systems (MIS) professional, or other programming personnel, to implement the query. If a user, for example, in a marketing department, wishes to investigate a potential new information relationship, he or she is often forced to cross department boundaries and as a result almost invariably experiences undesirable delays. As a result, much of the data is under utilized because many relations are never explored because the delay outweighs the benefit.
Moreover, because modern data warehouse systems are effectively customized database applications, they often inherit inefficiencies from the underlying database. These inefficiencies may be information related (e.g., inherently precluding certain lines of questioning because the application is tightly-coupled to the database's schema) or performance related (e.g., the system may be optimized for a certain type of transactional access that does not perform well to the accesses involved in the data warehousing queries).
More specifically, concerning performance related issues, most systems rely on the relational data model (RDM). The performance of a RDM implementation is typically limited by its “access method.” Commercially-available systems, for example, have their software logic rely on an access method (e.g., “B+tree”) that requires multiple accesses to storage (e.g., memory or disk) to obtain a given record. Some of the accesses are to reference structures that are used to effectively “point to” the data of interest (e.g., indices or hierarchies of linked lists). Sometimes, these reference structures can get so large that portions of the structure must reside on disk. Thus a given request for a database record may involve multiple disk storage requests. Moreover, the database operation algorithms are tightly bound to the access method. That is, the algorithm itself has been optimized to the access method and is thus dependent on the existence of the access method. Much of the literature on database performance explicitly or implicitly assumes the existence of such access methods.
Aside from the above limitations, most commercial systems are limited to the actual data within the database. The systems cannot query other important data elements such as the schema, the meta data, or the data dictionary without significant custom programming. Consequently, significant knowledge, e.g. useful queries, is not reported or available for use within such systems.
The above difficulties are exacerbated in the context of data residing on disparate databases.
Alternative approaches have been attempted. Childs, for example, discusses set-theoretic approaches in
Feasibility of a Set-Theoretic Data Structure: a General Structure Based on Reconstituted Definition of Relation
, Information Processing
68
, Edinburgh, 1968
; Description of a Set-Theoretic Data Structure
, Fall Joint Computer Conference, San Francisco, 1968; and
Extended Set Theory: a General Model for Very Large, Distributed, Backend Information Systems
. He is believed to have developed a system (STDS and XTDS) in which a user may express queries directly from a small set of set operators.
SUMMARY
Preferred embodiments of the invention provide a system for, and method of, exploring relationships in data stored in a computer readable medium. Under one preferred set of embodiments, sets of data are maintained in a computer readable medium and include at least one intensional expression and one extensional expression of at least one set resulting from an evaluation of a first query. A second query is transformed into a set program. It is then determined whether a sub-expression of the set program is satisfied by a maintained set. If so, the sub-expression is removed from the set program and the maintained set that satisfies the sub-expression of the set program is used.
Under another preferred set of embodiments, a query is received having at least one operator chosen from a set of operators that includes relational operators and having at least one input and output associated with the operator and defined as a table having at least one domain having a type associated therewith. The query is transformed into a set program having at least one operation structure, corresponding to the operator. An execution context is then analyzed to automatically select an operation structure from a set of operation structures corresponding to the operator so that the selected operation structure may be included in the set program.


REFERENCES:
patent: 4989132 (1991-01-01), Mellender et al.
patent: 5019961 (1991-05-01), Addesso et al.
patent: 5121494 (1992-06-01), Dias et al.
patent: 5193185 (1993-03-01), Lanter
patent: 5226111 (1993-07-01), Black et al.
patent: 5259066 (1993-11-01), Schmidt
patent: 5276870 (1994-01-01), Shan et al.
patent: 5301317 (1994-04-01), Lohman et al.
patent: 5307445 (1994-04-01), Dalal et al.
patent: 5325525 (1994-06-01), Shan et al.
patent: 5418942 (1995-05-01), Krawchuk et al.
patent: 5418943 (1995-05-01), Borgida et al.
patent: 5469568 (1995-11-01), Shiefer et al.
patent: 5481700 (1996-01-01), Thuraisingham
patent: 5495606 (1996-02-01), Borden et al.
patent: 5515531 (1996-05-01), Fujiwara et al.
patent: 5537590 (1996-07-01), Amado
patent: 5542073 (1996-07-01), Schiefer et al.
patent: 5546571 (1996-08-01), Shan et al.
patent: 5548749 (1996-08-01), Kroenke et al.
patent: 5548755 (1996-08-01), Leung et al.
patent: 5548770 (1996-08-01), Bridges
patent: 5555404 (1996-09-01), Torbjornsen et al.
patent: 5560006 (1996-09-01), Layden et al.
patent: 5574900 (1996-11-01), Huang et al.
patent: 5590319 (1996-12-01), Cohen et al.
patent: 5590321 (1996-12-01), Lin et al.
patent: 5615341 (1997-03-01), Agrawal et al.
patent: 5630124 (1997-05-01), Coyle, Jr. et al.
patent: 5655080 (1997-08-01), Dias et al.
patent: 5655116 (1997-08-01), Kirk et al.
patent: 5664171 (1997-09-01), Agrawal et al.
patent: 5664172 (1997-09-01), Antoshenkov
patent: 5666524 (1997-09-01), Kunkel et al.
patent: 5668986 (1997-09-01), Nilsen et al.
patent: 5687369 (1997-11-01), Li
patent: 5963932 (1999-10-01), Jakobsson et al.
patent: 6006224 (1999-12-01), McComb et al.
“Observer: An Approach for Query Procesing in Global Information Systems based on Interoperation across Pre-existing Ontologies,” Mena et al., Proceedings of the 1996 First International Conference on Cooperative Information Systems, Jun. 19-21, 1996, pag.*
Childs D.L., XTDS Set-Theoretic Development System Interactive Operations Guide, Version 1.0—Pre-Release Draft, Copyright Oct. 1, 1996 by Integrated Information Systems, Ann Arbor, MI (111 Pages).
Childs, D.L., Extended Axiomatic Set Theory For Modelling Mathematically Sound Software Systems, Draft Dated Apr. 2, 1991, Work Support, in Part, Through Research Contract withHewlett-Packard Laboratories (21 Pages).
Childs, D.L., Extended Axiomatic Set Theory A Focus on Functions, Draft Dated Mar. 26, 1994 (47 Pages).
Harinarayan et al., 1995 Database Theory, ICDT 1995, “Optimization Using Tuple Subsumption”.
Beeri et al., 1993 Proceedings of the ACM SIGMOD International Conference on Management of Dat

Affiliated with

Also associated with

Rating

Caching optimization with disk and/or memory cache management does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Caching optimization with disk and/or memory cache management, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Caching optimization with disk and/or memory cache management will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-2586185