On semantic issues connected with incomplete information databases

ABSTRACT

Various approaches to interpreting queries in a database with incomplete information are discussed. A simple model of a database is described, based on attributes which can take values in specified attribute domains. Information incompleteness means that instead of having a single value of an attribute, we have a subset of the attribute domain, which represents our knowledge that the actual value, though unknown, is one of the values in this subset. This extends the idea of Codd's null value, corresponding to the case when this subset is the whole attribute domain. A simple query language to communicate with such a system is described and its various semantics are precisely defined. We emphasize the distinction between two different interpretations of the query language—the external one, which refers the queries directly to the real world modeled in an incomplete way by the system, and the internal one, under which the queries refer to the system's information about this world, rather than to the world itself. Both external and internal interpretations are provided with the corresponding sets of axioms which serve as a basis for equivalent transformations of queries. The technique of equivalent transformations of queries is then extensively exploited for evaluating the interpretation of (i.e. the response to) a query.

REFERENCES

• 1: CHAMBERLIN, D.D., ASTRAHAN, M.M., ESWARAN, K.P., GRIFFITHS, P.P., LORIE, R.A., MEHL, J.W., REISNER, P., AND WADE, B.W. SEQUEL 2: A unified approach to data definition, manipulation, and control. IBM J. Res. Develop. 20 (1976), 560-575.
• 2: E. F. Codd, A relational model of data for large shared data banks, Communications of the ACM, v.13 n.6, p.377-387, June 1970 [doi>10.1145/362384.362685]
• 3: CODD, E.F. Understanding relations (Installment #7). FDT Bull. of ACM-SIGMOD 7, 3-4 (1975), 23-28.
• 4: GRANT, J. Null values in a relational data base. Inform. Process. Lett. 5 (1977), 156-157.
• 5: HAJEK, P. Automatic listing of important observational statements III. Kybernetika 10 (1974), 95-124.
• 6: HAJEK, P., BENDOV~., K., AND F~ENC, Z. The GUHA method and the three-valued logic. Kyber. netika 7 (1971), 421-435.
• 7: J AEGERMANN, M. Information storage and retrieval systems with incomplete information. I. Fund. Inform. 2 (1978), 17-41. (A preliminary version available as CC PAS Rep. 214, Warsaw, Poland, 1975.)
• 8: KLEENE, S.C. Introduction to Metamathematics. Noah-Holland Pub. Co., Amsterdam, 1952.
• 9: KONIKOWSKA, B. Data bases with incomplete information: On queries involving binary descriptors. To appear.
• 10: KONIKOWSKA, B., LIPSKI, W., MICHALEWICZ, Z., AND SENDOVA, E. An implementation of a data base with incomplete information I. To appear.
• 11: LIPSKI, W. On data bases with incomplete information. To appear.
• 12: LIPSKI, W. Informational systems with incomplete information. Proc. 3rd Int. Syrup. on Automata, Languages and Programming, Edinburgh, Scotland, 1976, pp. 120-130.
• 13: LIPSKI, W. On the logic of incomplete information. Proc. 6th Int. Symp. on Math. Foundations of Comptr. Sci., Tatransk~ Lomnica, Czechoslovakia, Sept. 1977, pp. 374-381.
• 14: LIPSKI, W. Informational systems: Semantic issues related to incomplete information, Part I. CC PAS Rep. 275, Warsaw, Poland, 1977.
• 15: LIPSKI, W., LODI, E., LuccIo, F., MUGNAI, C., AND PAGLI, L. 0n two dimensional data organization II. Fund. Inform. To appear.
• 16: LIPSKI, W., AND MAREK, W. On information storage and retrieval systems. In Mathematical Foundations of Computer Science, A. Mazurkiewicz and Z. Pawlak, Eds., Banach Center Publications, Vol. 2, Polish Scientific Publishers, Warsaw, Poland, 1977, pp. 215-259.
• 17: LIPSKI, W., AND MAREK, W. Information systems: On queries involving cardinalities. Inform. Syst. To appear.
• 18: LODI, E., LuccIo, F., MUGNAI, C., AND PAGLI, L. On two dimensional data organization I. Fund. Inform. To appear.
• 19: MAREK, W., AND PAWLAK, Z. Information storage and retrieval systems: Mathematical foundations. Theoret. Comptr. Sci. 1 (1976), 331-354.
• 20: MASEK, W. J. Some NP-complete set covering problems. Comptr. Sci. Lab., M.I.T., Cambridge, Mass., May 1978.
• 21: RASmWA, H., AND SIKORSKI, R. The Mathematics of Metamathematics. Polish Scientific Publishers, Warsaw, Poland, 1963.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.1 Logical Design
          Subjects: Data models

Additional Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages
          Subjects: Query languages
      H.2.4 Systems
          Subjects: Relational databases

General Terms:
Design, Languages

Keywords:
database, incomplete information, model logic, null values, query language semantics, relational model