Top-down statistical estimation on a database

ABSTRACT

The size of data sets subjected to statistical analysis is increasing as computer technology develops. Quick estimates of statistics rather than exact values are becoming increasingly important to analysts. We propose a new technique for estimating statistics on a database, a "top-down" alternative to the "bottom-up" method of sampling. This approach precomputes a set of general-purpose statistics on the database, a "database abstract", and then uses a large set of inference rules to make bounded estimates of other, arbitrary statistics requested by users. The inference rules form a new example of an artificial-intelligence "expert system". There are several important advantages of this approach over sampling methods.

REFERENCES

• 1: Doug Bates , Haran Boral , David J. DeWitt, A framework for research in database management for statistical analysis or a primer on statistical database management problems for computer scientists, Proceedings of the 1982 ACM SIGMOD international conference on Management of data, June 02-04, 1982, Orlando, Florida [doi>10.1145/582353.582365]
• 2: Stavros Christodoulakis. Estimating Selectivities in Data Bases. Technical Report CSRG-136, University of Toronto, December, 1981.
• 3: A. J. Cole and R. Morrison. Triplex: A System for Interval Arithmetic. Software --- Practice and Experience 12:341--350, 1982.
• 4: Randall Davis and Jonathan King. An Overview of Production Systems. In E. W. Elcock and D. Michie (editors), Machine Intelligence 8, pages 300--334. Wiley, New York, 1976.
• 5: Philip E. Gill, Walter Murray, and Margaret H. Wright. Practical Optimization. Academic Press, New York, 1981.
• 6: Peter E. Hart, Directions for AI in the eighties, ACM SIGART Bulletin [doi>10.1145/1056663.1056664]
• 7: Edward B. Haugen. Probabilistic Approaches to Design. Wiley, New York, 1968.
• 8: S. Koenig and R. Paige. A Transformational Framework for the Automatic Control of Derived Data. In Proceedings of the 7th Meeting, pages 306--318. International Conference on Very Large Data Bases, Cannes, France, 1981.
• 9: Douglas B. Lenat. The Nature of Heuristics. Artificial Intelligence 19:189--249, 1982.
• 10: J. McDermott, A. Newell, and J. Moore. The Efficiency of Certain Production System Implementations. In D. A. Waterman and F. Hayes-Roth (editors), Pattern-Directed Inference Systems, pages 155--176. Academic Press, New York, 1978.
• 11: Jacob Paul Morgenstein, Computer based management information systems embodying answer accuracy as a user parameter, 1981
• 12: L. B. Rall. Interval Analysis: A Tool For Applied Mathematics. Technical Report 2268, University of Wisconsin Mathematics Research Center, 1981.
• 13: Neil C. Rowe, Rule/based statistical calculations on a "Database abstract", Proceedings of the 1st LBL Workshop on Statistical database management, p.163-175, December 02-04, 1981, Melno Park, California
• 14: Neil C. Rowe. Inheritance of Statistical Properties. In Proceedings of the National Conference, pages 221--224. American Association for Artificial Intelligence, Pittsburgh PA, August, 1982.
• 15: Neil C. Rowe. Diophantine Compromise of a Statistical Database. In Three Papers on Rule-Based Estimation of Statistics on a Database, chapter 3. Stanford University Computer Science Department report 948, 1982.
• 16: Neil C. Rowe, Some experiments in evaluation of an expert system for statistical estimation on databases, Proceedings of the 2nd international workshop on Proceedings of the Second International Workshop on Statistical Database Management, p.235-244, September 27-29, 1983, Los Altos, California
• 17: Neil Charles Rowe, Rule-based statistical calculations on a database abstract, 1983
• 18: John E. Shore and Rodney W. Johnson. Properties of Cross-Entropy Minimization. IEEE Transactions on Information Theory IT-27(4):472--482, July, 1981.
• 19: Arie Shoshani, Statistical Databases: Characteristics, Problems, and some Solutions, Proceedings of the 8th International Conference on Very Large Data Bases, p.208-222, September 08-10, 1982
• 20: John W. Tukey. Exploratory Data Analysis. Addison-Wesley, Reading, Mass., 1977.
• 21: Adrian Walker. On Retrieval From a Small Version of a Large Data Base. In Proceedings of the 6th Meeting, pages 47--54. International Conference on Very Large Data Bases, 1980.