Incomplete information costs and database design

ABSTRACT

This paper presents a methodology for trading-off the cost of incomplete information against the data-related costs in the design of database systems. It investigates how the usage patterns of the database, defined by the characteristics of information requests presented to it, affect its conceptual design. The construction of minimum-cost answers to information requests for a variety of query types and cost structures is also studied. The resulting costs of incomplete database information are balanced against the data-related costs in the derivation of the optimal design.

REFERENCES

• 1: CHEN, P. P., AND YAO, S.B. Design and performance tools for database systems. In Proceedings of the International Conference on Very Large Databases, 1977, 3-15.
• 2: D. Chow , C. T. Yu, On the Construction of Feedback Queries, Journal of the ACM (JACM), v.29 n.1, p.127-151, Jan. 1982 [doi>10.1145/322290.322299]
• 3: E. F. Codd, Extending the database relational model to capture more meaning, ACM Transactions on Database Systems (TODS), v.4 n.4, p.397-434, Dec. 1979 [doi>10.1145/320107.320109]
• 4: HEINE, M. H. Design equations for retrieval systems based on the Swets model. J. Am. Soc. Inf. Sci. 25 (1974), 183-198.
• 5: Tomasz Imieliński , Witold Lipski, Jr., Incomplete Information in Relational Databases, Journal of the ACM (JACM), v.31 n.4, p.761-791, Oct. 1984 [doi>10.1145/1634.1886]
• 6: KARLIN, S., AND TAYLOR, H.M. A First Course in Stochast& Processes. Academic Press, New York, 1975.
• 7: KRAFT, D.H. A threshold rule applied to the retrieval decision model. J. Am. Soc. Inf. Sci. 29 (1978), 77-80.
• 8: KRAFT, D. H., AND BOOKSTEIN, A. Evaluation of information retrieval systems: A decision theory approach. J. Am. Soc. Inf. Sci. 29 (1978), 31-40.
• 9: Witold Lipski, Jr., On semantic issues connected with incomplete information databases, ACM Transactions on Database Systems (TODS), v.4 n.3, p.262-296, Sept. 1979 [doi>10.1145/320083.320088]
• 10: Witold Lipski, Jr., On Databases with Incomplete Information, Journal of the ACM (JACM), v.28 n.1, p.41-70, Jan. 1981 [doi>10.1145/322234.322239]
• 11: David Maier, Theory of Relational Databases, Computer Science Pr, 1983
• 12: MARSCHAK, J., AND RADNER, R. Economic Theory o{ Teams. Yale University Press, New Haven, Conn., 1972.
• 13: Gerard Salton, Dynamic information and library processing, Prentice-Hall, Inc., Upper Saddle River, NJ, 1975
• 14: G. Salton , C. Buckley , C. T. Yu, An evaluation of term dependence models in information retrieval, Proceedings of the 5th annual ACM conference on Research and development in information retrieval, p.151-173, May 18-20, 1982, West Berlin, Germany
• 15: SCHKOLNICK, M. A survey of physical database design methodology and techniques. In Proceedings of the International Conference on Very Large Databases, 1978, 474-487.
• 16: SWETS, J.A. Information retrieval systems. Science 241 (1963), 245-250.
• 17: SWETS, J.A. Effectiveness of information retrieval methods. Am. Doc. 20 (1969), 72-89.
• 18: Jeffrey D. Ullman, Principles of Database Systems, W. H. Freeman & Co., New York, NY, 1983
• 19: Yannis Vassiliou, Null values in data base management a denotational semantics approach, Proceedings of the 1979 ACM SIGMOD international conference on Management of data, May 30-June 01, 1979, Boston, Massachusetts [doi>10.1145/582095.582123]
• 20: VASS{LIOU, Y. Functional dependencies and incomplete information. In Proceedings of the 6th International Conference on Very Large Databases (Montreal, Oct. 1-3, 1980), ACM, New York, 260-269.
• 21: WINKLER, R. L., AND HAYS, W.L. Statistics. Holt, Rinehart & Winston, New York, 1975.
• 22: Eugene Wong, A statistical approach to incomplete information in database systems, ACM Transactions on Database Systems (TODS), v.7 n.3, p.470-488, Sept. 1982 [doi>10.1145/319732.319747]
• 23: Yu, C. T., LUK, W. S., AND SIu, M.K. On models of information retrieval. In{. Syst. 4 (1979), 205-218.

INDEX TERMS

Classification:
  H. Information Systems
  H.1 MODELS AND PRINCIPLES
  H.2 DATABASE MANAGEMENT
  H.3 INFORMATION STORAGE AND RETRIEVAL

General Terms:
Design, Economics, Theory