Witold Lipski
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.
- 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.Google Scholar
- 2 CODD, E.F. A relational model of data for large shared data banks. Comm. ACM 13, 6 (June 1970), 377-387. Google ScholarDigital Library
- 3 CODD, E.F. Understanding relations (Installment #7). FDT Bull. of ACM-SIGMOD 7, 3-4 (1975), 23-28.Google Scholar
- 4 GRANT, J. Null values in a relational data base. Inform. Process. Lett. 5 (1977), 156-157.Google ScholarCross Ref
- 5 HAJEK, P. Automatic listing of important observational statements III. Kybernetika 10 (1974), 95-124.Google Scholar
- 6 HAJEK, P., BENDOV~., K., AND F~ENC, Z. The GUHA method and the three-valued logic. Kyber. netika 7 (1971), 421-435.Google Scholar
- 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.)Google Scholar
- 8 KLEENE, S.C. Introduction to Metamathematics. Noah-Holland Pub. Co., Amsterdam, 1952.Google Scholar
- 9 KONIKOWSKA, B. Data bases with incomplete information: On queries involving binary descriptors. To appear.Google Scholar
- 10 KONIKOWSKA, B., LIPSKI, W., MICHALEWICZ, Z., AND SENDOVA, E. An implementation of a data base with incomplete information I. To appear.Google Scholar
- 11 LIPSKI, W. On data bases with incomplete information. To appear.Google Scholar
- 12 LIPSKI, W. Informational systems with incomplete information. Proc. 3rd Int. Syrup. on Automata, Languages and Programming, Edinburgh, Scotland, 1976, pp. 120-130.Google Scholar
- 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.Google ScholarCross Ref
- 14 LIPSKI, W. Informational systems: Semantic issues related to incomplete information, Part I. CC PAS Rep. 275, Warsaw, Poland, 1977.Google Scholar
- 15 LIPSKI, W., LODI, E., LuccIo, F., MUGNAI, C., AND PAGLI, L. 0n two dimensional data organization II. Fund. Inform. To appear.Google Scholar
- 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.Google Scholar
- 17 LIPSKI, W., AND MAREK, W. Information systems: On queries involving cardinalities. Inform. Syst. To appear.Google Scholar
- 18 LODI, E., LuccIo, F., MUGNAI, C., AND PAGLI, L. On two dimensional data organization I. Fund. Inform. To appear.Google Scholar
- 19 MAREK, W., AND PAWLAK, Z. Information storage and retrieval systems: Mathematical foundations. Theoret. Comptr. Sci. 1 (1976), 331-354.Google ScholarCross Ref
- 20 MASEK, W. J. Some NP-complete set covering problems. Comptr. Sci. Lab., M.I.T., Cambridge, Mass., May 1978.Google Scholar
- 21 RASmWA, H., AND SIKORSKI, R. The Mathematics of Metamathematics. Polish Scientific Publishers, Warsaw, Poland, 1963.Google Scholar
Index Terms
- On semantic issues connected with incomplete information databases
Recommendations
Querying Incomplete Information Using Bag Relational Algebra
EKNOW '10: Proceedings of the 2010 Second International Conference on Information, Process, and Knowledge ManagementIn the paper, we introduce bag relational algebra with grouping and aggregation overa particular representation of incomplete information called c-tables, which wasfirst introduced byGrahne in 1984.In order for this algebra to be closed and ``well-...
On deductive databases with incomplete information
In order to extend the ability to handle incomplete information in a definite deductive database, a Horn clause-based system representing incomplete information as incomplete constants is proposed. By using the notion of incomplete constants the ...
SQL’s Three-Valued Logic and Certain Answers
Invited Paper from ICDT 2015, SIGMOD 2014, EDBT 2014 and Regular PapersThe goal of the article is to bridge the difference between theoretical and practical approaches to answering queries over databases with nulls. Theoretical research has long ago identified the notion of correctness of query answering over incomplete ...
Comments