Intelligent database caching through the use of page-answers and page-traces

ABSTRACT

In this paper a new method to improve the utilization of main memory systems is presented. The new method is based on prestoring in main memory a number of query answers, each evaluated out of a single memory page. To this end, the ideas of page-answers and page-traces are formally described and their properties analyzed. The query model used here allows for selection, projection, join, recursive queries as well as arbitrary combinations. We also show how to apply the approach under update traffic. This concept is especially useful in managing the main memories of an important class of applications. This class includes the evaluation of triggers and alerters, performance improvement of rule-based systems, integrity constraint checking, and materialized views. These applications are characterized by the existence at compile time of a predetermined set of queries, by a slow but persistent update traffic, and by their need to repetitively reevaluate the query set. The new approach represents a new type of intelligent database caching, which contrasts with traditional caching primarily in that the cache elements are derived data and as a consequence, they overlap arbitrarily and do not have a fixed length. The contents of the main memory cache are selected based on the data distribution within the database, the set of fixed queries to preprocess, and the paging characteristics. Page-answers and page-traces are used as the smallest indivisible units in the cache. An efficient heuristic to select a near optimal set of page-answers and page-traces to populate the main memory has been developed, implemented, and tested. Finally, quantitative measurements of performance benefits are reported.

REFERENCES

• 1: José A. Blakeley , Neil Coburn , Per-Åke Larson, Updating Derived Relations: Detecting Irrelevant and Autonomously Computable Updates, Proceedings of the 12th International Conference on Very Large Data Bases, p.457-466, August 25-28, 1986
• 2: Jose A. Blakeley , Per-Ake Larson , Frank Wm Tompa, Efficiently updating materialized views, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.61-71, May 28-30, 1986, Washington, D.C., United States
• 3: Jonathan Bein , Roger King, MOBY: An Architecture for Distributed Expert Database Systems, Proceedings of the 13th International Conference on Very Large Data Bases, p.13-20, September 01-04, 1987
• 4: BLUM, M., FLOYD, R. W., PRATT, V., RlVEST, R. L., AND TARJAN, R. E T~me bounds for selection. J. Comput. Syst. Scl. 7 (1973) 448-461.
• 5: CHAKRAVARTHY, U. S., AND MINKER, J. Processing multiple querms m database systems. IEEE Quart. Bull. Database Eng. 5.3 (Sept. 1982), 38-43.
• 6: Upen S. Chakravarthy , Jack Minker, Multiple Query Processing in Deductive Databases using Query Graphs, Proceedings of the 12th International Conference on Very Large Data Bases, p.384-391, August 25-28, 1986
• 7: Stavros Christodoulakis, Estimating block transfers and join sizes, Proceedings of the 1983 ACM SIGMOD international conference on Management of data, May 23-26, 1983, San Jose, California
• 8: CHRISTODOULAKIS, S. Estimating block selectivities. In Inf. Syst. 9, 1 (,Jan. 1984), 69-79.
• 9: S. Christodoulakis, Implications of certain assumptions in database performance evauation, ACM Transactions on Database Systems (TODS), v.9 n.2, p.163-186, June 1984 [doi>10.1145/329.318578]
• 10: D. Cohen, Compiling complex database transition triggers, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.225-234, June 1989, Portland, Oregon, United States
• 11: DEWITT, D. J., KATZ, R. H., OLKEN, F., SHAPIRO, L., STONEBRAKER, M. R., AND WOOD, D. Implementation techniques for main memory database systems. In Proceedings of the lOth VLDB (Singapore, Aug. 1984), pp. 1 8.
• 12: Klaus Elhardt , Rudolf Bayer, A database cache for high performance and fast restart in database systems, ACM Transactions on Database Systems (TODS), v.9 n.4, p.503-525, Dec. 1984 [doi>10.1145/1994.1995]
• 13: Sheldon Finkelstein, Common expression analysis in database applications, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582400]
• 14: FORGY, C. L. Rete: A fast algorithm for the many pattern/many object pattern match problem. Art~f. Intell. 19, (1982), 17-37.
• 15: HAMMER, M., AND CHAN, A. Index selection in a self-adaptive database management system. In Procee&ngs of the 3rd VLDB (Brussels, Aug. 1976), pp. 1-8.
• 16: IP, M. Y. L., SAXTON, L. g., AND RAGHAVAN, V. g. On the selection of an optimal set of indexes. IEEE Trans. Softw. Eng. (Mar. 1983).
• 17: Matthias Jarke , Jurgen Koch, Query Optimization in Database Systems, ACM Computing Surveys (CSUR), v.16 n.2, p.111-152, June 1984 [doi>10.1145/356924.356928]
• 18: JARKE, M. Common subexpression isolation in multiple query optimization. In Query Processing in Database Systems, W. Kim, D. Reiner, and D. Batory, Eds., Springer, New York, 1985, pp. 191 205.
• 19: KAMEL, N. Performance enhancements of Rete networks through the use of page-nodes. In Proceedings of the 3rd IEEE Conference on Art,ficzal Intelhgence Apphcatzons (Orlando, Fla., 1987).
• 20: Nabil Nessim Kamel, The use of controlled redundancy in self-adaptive databases (temporaries, derived, packrat, r-tree, texture analysis), 1985
• 21: KAMEL, N., AND KING, R. Optimal management of temporaries in distributed databases. In Proceedings of the Supercomputing Conference (Santa Clara, Calif., 1987), pp. 188-193.
• 22: KAMEL, N., AND KING, R. PACKRAT as a tool for enhancing retrieval support for permanent CAD databases. In Proceedings of the Internatzonal Conference on Data and Knowledge Systems for Engineering and Manufacturing (Hartford, Conn., Oct. 1988).
• 23: R. H. Katz , E. Wong, Rosolving conflicts in global storage design through replication, ACM Transactions on Database Systems (TODS), v.8 n.1, p.110-135, March 1983 [doi>10.1145/319830.319836]
• 24: Kou, L.T. Polynomial complete consecutive information retrieval problems. In SIAM J. Comput. 6, 1 (Mar. 1977), 67-75.
• 25: LARSON, P.-A., AND YANG, H.Z. Computing queries from derived relatmns. In Proceedings of the llth VLDB (Stockholm, Aug. 1980), pp. 259-269.
• 26: Tobin J. Lehman , Michael J. Carey, A Study of Index Structures for Main Memory Database Management Systems, Proceedings of the 12th International Conference on Very Large Data Bases, p.294-303, August 25-28, 1986
• 27: Samy Mahmoud , J. S. Riordon, Optimal allocation of resources in distributed information networks, ACM Transactions on Database Systems (TODS), v.1 n.1, p.66-78, March 1976 [doi>10.1145/320434.320449]
• 28: MENDENHALL, W., SCHEAFFER, R. L., AND WACKERLY, D.D. Mathemat,cal Statistics wzth Applications. Duxbury Press, Boston, Mass., 1981, pp. 317 320.
• 29: NICOLAS, J.-M. Logic for improving integrity checking in relational data bases. Acts Inf. 18, 3 (Dec. 1982), 227 253.
• 30: Anthony B. O'Hare , Amit P. Sheth, The interpreted-compiled range of AI/DB systems, ACM SIGMOD Record, v.18 n.1, p.32-42, March 1989 [doi>10.1145/382272.382273]
• 31: Xiaolei Qian , Gio Wiederhold, Knowledge-based Integrity Constraint Validation, Proceedings of the 12th International Conference on Very Large Data Bases, p.3-12, August 25-28, 1986
• 32: ROSENKRANTZ, D., AND HUNT, III, H.B. Processing conjunctive predicates and queries. In Proceedings of the 6th VLDB (Montreal, Oct. 1980), pp. 64 72.
• 33: Nicholas Roussopoulos, View indexing in relational databases, ACM Transactions on Database Systems (TODS), v.7 n.2, p.258-290, June 1982 [doi>10.1145/319702.319729]
• 34: Barbara G. Ryder , Marvin C. Paull, Elimination algorithms for data flow analysis, ACM Computing Surveys (CSUR), v.18 n.3, p.277-316, Sept. 1986 [doi>10.1145/27632.27649]
• 35: Giovanni Maria Sacco , Mario Schkolnick, Buffer management in relational database systems, ACM Transactions on Database Systems (TODS), v.11 n.4, p.473-498, Dec. 1986 [doi>10.1145/7239.7336]
• 36: Giovanni Maria Sacco , Mario Schkolnick, A Mechanism for Managing the Buffer Pool in a Relational Database System Using the Hot Set Model, Proceedings of the 8th International Conference on Very Large Data Bases, p.257-262, September 08-10, 1982
• 37: R. Sedgewick, Algorithms (2nd ed.), Addison-Wesley Longman Publishing Co., Inc., Boston, MA, 1988
• 38: Timos K. Sellis, Global query optimization, Proceedings of the 1986 ACM SIGMOD international conference on Management of data, p.191-205, May 28-30, 1986, Washington, D.C., United States
• 39: Timos K. Sellis, Multiple-query optimization, ACM Transactions on Database Systems (TODS), v.13 n.1, p.23-52, March 1988 [doi>10.1145/42201.42203]
• 40: T. Sellis , C. C. Lin , L. Raschid, Implementing large production systems in a DBMS environment: concepts and algorithms, Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.404-423, June 01-03, 1988, Chicago, Illinois, United States
• 41: Dennis G. Severance , Guy M. Lohman, Differential files: their application to the maintenance of large databases, ACM Transactions on Database Systems (TODS), v.1 n.3, p.256-267, Sept. 1976 [doi>10.1145/320473.320484]
• 42: SHETH, A., BUER, D. V., STEPHEN, RUSSELL, S. AND DAO, S. Cache management system: Preliminary design and evaluation criteria. Tech. Rep. TM-8484/000/00, Unlsys Corp., West Coast Research Center (Oct. 1988).
• 43: SHETH, A. P., AND O'HARE, A.B. The architecture of BRAID: A system for efficient AI/DB Integration. Tech. Mem. TM-STS-015544, Bellcore, Nov. 1989.
• 44: Ben Shneiderman, Batched searching of sequential and tree structured files, ACM Transactions on Database Systems (TODS), v.1 n.3, p.268-275, Sept. 1976 [doi>10.1145/320473.320487]
• 45: Michael Stonebraker , Gerald Held , Eugene Wong , Peter Kreps, The design and implementation of INGRES, ACM Transactions on Database Systems (TODS), v.1 n.3, p.189-222, Sept. 1976 [doi>10.1145/320473.320476]
• 46: Xian-He Sun , Nabil Kamel , Lionel M. Ni, Solving implication problems in database applications, Proceedings of the 1989 ACM SIGMOD international conference on Management of data, p.185-192, June 1989, Portland, Oregon, United States
• 47: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 48: Jeffrey D. Ullman, Principles of database and knowledge-base systems, Vol. I, Computer Science Press, Inc., New York, NY, 1988
• 49: Gio C. Wiederhold, Database Design, McGraw-Hill, Inc., New York, NY, 1977
• 50: Eugene Wong , Karel Youssefi, Decomposition—a strategy for query processing, ACM Transactions on Database Systems (TODS), v.1 n.3, p.223-241, Sept. 1976 [doi>10.1145/320473.320479]
• 51: S. B. Yao, Approximating block accesses in database organizations, Communications of the ACM, v.20 n.4, p.260-261, April 1977 [doi>10.1145/359461.359475]
• 52: YOUSSEFI, K., AND WONG, E. Query processing in a relational database management system In Proceedzngs of the 5th VLDB (Rio de Janero, Oct. 1979), pp. 409 417.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.2 Physical Design
          Subjects: Access methods
      H.2.4 Systems
          Subjects: Query processing
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.1 Content Analysis and Indexing
          Subjects: Indexing methods
      H.3.2 Information Storage
          Subjects: Record classification**

  I. Computing Methodologies
  I.1 SYMBOLIC AND ALGEBRAIC MANIPULATION
      I.1.3 Languages and Systems
          Subjects: Evaluation strategies
  I.2 ARTIFICIAL INTELLIGENCE
      I.2.8 Problem Solving, Control Methods, and Search
          Subjects: Plan execution, formation, and generation

General Terms:
Algorithms, Design, Performance

Keywords:
artificial intelligence, databases, page access