Abstract
This paper deals with the modeling and querying of a database containing uncertain attribute values, in the situation where some knowledge is available about the more or less certain value (or disjunction of values) that a given attribute in a given tuple can take. This is represented in the setting of possibility theory. A relational database model suited to this context is introduced, and selection, join and union operators of relational algebra are extended so as to handle such relations. It is shown that i) the model in question is a strong representation system for the algebraic operators considered, and that ii) the data complexity associated with the extended operators in this context is the same as in the classical database case, which makes the approach highly scalable. A possibilistic logic encoding of the model is also outlined.
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
Abiteboul, S., Hull, R., Vianu, V.: Foundations of Databases. Addison-Wesley, Reading (1995)
Antova, L., Jansen, T., Koch, C., Olteanu, D.: Fast and simple processing of uncertain data. In: Proc. of ICDE 2008, pp. 983–992 (2008)
Benjelloun, O., Das Sarma, A., Halevy, A., Widom, J.: ULDBs: Databases with uncertainty and lineage. In: Proc. VLDB 2006, pp. 953–964 (2006)
Bosc, P., Pivert, O.: About projection-selection-join queries addressed to possibilistic relational databases. IEEE Trans. on Fuzzy Systems 13, 124–139 (2005)
Codd, E.F.: Extending the relational database model to capture more meaning. ACM Transactions on Database Systems 4(4), 397–434 (1979)
Dalvi, N., Suciu, D.: Management of probabilistic data: Foundations and challenges. In: Proc. of PODS 2007, pp. 1–12 (2007)
Das Sarma, A., Benjelloun, O., Halevy, A., Widom, J.: Working models for uncertain data. In: Proc. of 22nd Int. Conf. on Data Engineering, ICDE (2006)
Dubois, D., Prade, H.: Necessity measures and the resolution principle. IEEE Trans. Syst., Man and Cyber. 17, 474–478 (1987)
Dubois, D., Prade, H.: Possibility Theory. Plenum, New York (1988)
Dubois, D., Lang, J., Prade, H.: Automated reasoning using possibilistic logic: Semantics, belief revision, and variable certainty weights. IEEE Transactions on Knowledge and Data Engineering 6(1), 64–71 (1994)
Eiter, T., Lukasiewicz, T., Walter, M.: Extension of the relational algebra to probabilistic complex values. In: Schewe, K.-D., Thalheim, B. (eds.) FoIKS 2000. LNCS, vol. 1762, pp. 94–115. Springer, Heidelberg (2000)
Green, C.: Theorem-proving by resolution as a basis for question-answering systems. In: Michie, D., Meltzer, B. (eds.) Machine Intellig., vol. 4, pp. 183–205. Edinb. Uni. Pr. (1969)
Green, T.J., Tannen, V.: Models for incomplete and probabilistic information. IEEE Data Eng. Bull. 29, 17–24 (2006)
Imielinski, T., Lipski, W.: Incomplete information in relational databases. J. of the ACM 31, 761–791 (1984)
Lakshmanan, L., Leone, N., Ross, R., Subrahmanian, V.S.: Probview: A flexible probabilistic system. ACM Trans. Database Syst. 22(3), 419–469 (1997)
Lipski, W.: Semantic issues connected with incomplete information databases. ACM Transactions on Database Systems 4(3), 262–296 (1979)
Prade, H., Testemale, C.: Generalizing database relational algebra for the treatment of incomplete/uncertain information and vague queries. Information Sciences 34, 115–143 (1984)
Ré, C., Dalvi, N., Suciu, D.: Query evaluation on probabilistic databases. IEEE Data Eng. Bull. 29, 25–31 (2006)
Zadeh, L.A.: Fuzzy sets as a basis for a theory of possibility. Fuzzy Sets and Systems 1, 3–28 (1978)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2009 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Bosc, P., Pivert, O., Prade, H. (2009). A Model Based on Possibilistic Certainty Levels for Incomplete Databases. In: Godo, L., Pugliese, A. (eds) Scalable Uncertainty Management. SUM 2009. Lecture Notes in Computer Science(), vol 5785. Springer, Berlin, Heidelberg. https://doi.org/10.1007/978-3-642-04388-8_8
Download citation
DOI: https://doi.org/10.1007/978-3-642-04388-8_8
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-642-04387-1
Online ISBN: 978-3-642-04388-8
eBook Packages: Computer ScienceComputer Science (R0)