J. M. Morrissey
Abstract
Information systems exist to model, store, and retrieve all types of data. Problems arise when some of the data are missing or imprecisely known or when an attribute is not applicable to a particular object. A consistent and useful treatment of such exceptions is necessary. The approach taken here is to allow any attribute value to be a regular precise value, a string denoting that the value is missing, a string denoting that the attribute is not applicable, or an imprecise value. The imprecise values introduce uncertainty into query evaluation, since it is no longer obvious which objects should be retrieved. To handle the uncertainty, two set of objects are retrieved in response to every query: the set of objects that are known to satisfy with complete certainty and the set that possibly satisfies the query with various degrees of uncertainty. Two methods of estimating this uncertainty, based on information theory, are proposed. The measure of uncertainty is used to rank objects for presentation to a user.
- 1 CARDELLI, L. A semantics of multiple inheritance. In Semantics of Data Types. Lecture Notes in Computer Science 173, Springer, New York, 1984. Google Scholar
- 2 CODD, E. F. Understanding relations. ACM SIGMOD 7 (1975), 23-28.Google Scholar
- 3 CODD, E.F. Extending the database relational model to capture more meaning. A CM Trans. Database Syst. 4, 4 (Dec. 1979), 394-434. Google Scholar
- 4 CODD, E.F. Missing information (applicable and inapplicable) in relational systems. SIGMOD Rec. 15, 4 (Dec. 1986). Google Scholar
- 5 DATE, C.J. Null values in databases, in Proceedings of the 2nd British National Conference on Databases (1982).Google Scholar
- 6 GRAHNE, G. Dependency satisfaction in databases with incomplete information. In Proceedings of the lOth International Conference on Very Large Data Bases (1981), 37-45. Google Scholar
- 7 GRAHNE, G. Horn tables--An efficient tool for handling incomplete information in databases. In Proceedings of the 8th A CM SIGA CT-SIGMOD-SIGART Symposium on Principles o{ Database Systems (1989), 75-82. Google Scholar
- 8 GRAY, M. Views and imprecise information in databases. Ph.D. thesis, Cambridge Univ., Cambridge, England (Nov. 1982).Google Scholar
- 9 HARPER, D. J. ET AL. MINSTREL-ODM: A basic office data model. In{. Process. Manage. 22, 2 (1986), 83-107. Google Scholar
- 10 HOUGAARD, P., AND MCALPINE, G. A graphical user interface for an office filing and retrieval facility. In Proceedings of ESPRIT Technical Week (1985).Google Scholar
- 11 IMELINSKI, T., AND LIPSKI, W. On representing incomplete information in a relational database. In Proceedings of the 7th International Conference on Very Large Data Bases (1981), 388-397.Google Scholar
- 12 IMELINSKI, T., AND LIPSK{, W. Incomplete information in relational databases. J. ACM 31, 4 (1984), 701-791. Google Scholar
- 13 LEVESQUE, H. A formal treatment of incomplete knowledge bases. Ph.D. thesis, Dept. of Computer Science, Univ. of Toronto, 1981. Google Scholar
- 14 LEVESQUE, H. The interaction with incomplete knowledge bases: A formal treatment. In Proceedings of the International Joint Conference on Artificial Intelligence (Vancouver, B.C., 1981).Google Scholar
- 15 LEVESQUE, H. The logic of incomplete knowledge bases. In On Conceptual Modelling: Perspectives from Arti{icial Intelligence, Databases, and Programming Languages, M. L. Brodie, J. Mylopoulos, and J. Schmidt, Eds. Springer, New York, 1984.Google Scholar
- 16 LIPSKI, W. On semantic issues connected with incomplete information databases. ACM Trans. Database Syst. 4, 3 (Sept. 1979), 262-296. Google Scholar
- 17 MORRISSEY, J.M. A treatment of imprecise data and uncertainty in information systems. Ph.D. thesis, National Univ. of Ireland, Aug. 1987.Google Scholar
- 18 SHAFER, G. A Mathematical Theory of Evidence. Princeton University Press, Princeton, N.J., 1976.Google Scholar
- 19 SHORTLIFFE, E. H., AND BUCHANAN, B.G. A model of inexact reasoning in medicine. Math. Biosci. 23 (1975), 351-379.Google Scholar
- 20 SMEATON, A.F. Using parsing of natural langauge as a part of document retrieval. Ph.D. thesis, National Univ. of Ireland, 1987.Google Scholar
- 21 ULLMAN, J. Universal relation interfaces for database systems. In Information Processing "83, R. E. A. Mason, Ed. Elsevier Science, B.V. (North Holland), Amsterdam, 1983.Google Scholar
- 22 VAN RIJSBERGEN, C.J. A non-classical logic for information retrieval. Comput. J. 29, 6 (1986), 481-485.Google Scholar
- 23 VASSlUOU, Y. Null values in database management: A denotational semantics approach. In Proceedings of the 1979 A CM SIGMOD International Conference on Management of Data (Boston, 1979). Google Scholar
- 24 VASSILIOU, V. A formal treatment of imperfect information in database management. Ph.D. thesis, Univ. of Toronto, Sept. 1980. Google Scholar
- 25 WILLIAMS, M. H., AND NICHOLSON, S.A. An approach to handling incomplete information in databases. Comput. J. 31, 2 (1988), 133-140. Google Scholar
- 26 WINSLETT, M. A model based approach to updating databases with incomplete information. ACM Trans. Database Syst. 13, 2 (1988), 167-196. Google Scholar
- 27 ZADEH, L. Fuzzy sets. In{. Control 8 (1965), 338-353.Google Scholar
- 28 ZADEH, L. Fuzzy sets as a basis for a theory of possibility. In Fuzzy Sets and Systems, North- Holland, Amsterdam, 1978.Google Scholar
- 29 ZADEH, L. Commonsense knowledge representation based on fuzzy logic. Comput. 16, 10 (1983), 61-65.Google Scholar
- 30 ZANIOLO, C. Database relations with null values. J. Comput. Syst. Sci. 28 (1984), 142-166.Google Scholar
- 31 ZLOOF, M.M. Query-By-Example: A database language. IBM Syst. J. 16 (1977), 324-343.Google Scholar
Index Terms
- Imprecise information and uncertainty in information systems
Recommendations
On Measuring Uncertainty and Uncertainty-Based Information: Recent Developments
It is shown in this paper how the emergence of fuzzy set theory and the theory of monotone measures considerably expanded the framework for formalizing uncertainty and suggested many new types of uncertainty theories. The paper focuses on issues ...
Imprecise second-order hierarchical uncertainty model
A hierarchical uncertainty model for combining different evidence is studied in the paper. The model is general enough for many applications. The presented approach for dealing with the model allows us to combine the available heterogeneous information ...
Measures of uncertainty for imprecise probabilities: An axiomatic approach
The aim of this paper is to formalize, within a broad range of theories of imprecise probabilities, the notion of a total, aggregate measure of uncertainty and its various disaggregations into measures of nonspecificity and conflict. As a framework for ...
Reviews
Karen Sparck-Jones
Awkward database queries are those for which values are imprecise (with respect to domain or range) or unknown, or attributes are inapplicable. Being able to deal satisfactorily with data distinctions of this kind is important for real applications. Morrissey claims that this approach is an advance on earlier work in offering both an appropriate and coherent semantics for query evaluation covering the different cases and an operational measure of uncertainty for ordering retrieved data that do not precisely satisfy the query. The form of data representation and method of query evaluation for different simple and complex types of query are described in detail, showing how first precise and then imprecise data sets are retrieved. The members of the second set can in turn be ranked by their degree of uncertainty, using information-theoretic measures based on either self-information or entropy. The paper is clearly written and well illustrated by examples. The way the different kinds of data are retrieved looks convincing. Unfortunately the treatment of uncertainty, though implemented for a prototype office information system, has not been seriously tested. Such testing is clearly essential, as approaches of the kind presented all tend to look plausible but need to be subjected to the hard reality of actual hairy data to demonstrate their solidity. The paper is nevertheless an interesting start and, as it gives a clear and detailed account of the author's work, a useful introduction to the area.
Access critical reviews of Computing literature here
Become a reviewer for Computing Reviews.
Comments