Abstract
Possibility theory is applied to introduce and reason about the fundamental notion of a key for uncertain data. Uncertainty is modeled qualitatively by assigning to tuples of data a degree of possibility with which they occur in a relation, and assigning to keys a degree of certainty which says to which tuples the key applies. The associated implication problem is characterized axiomatically and algorithmically. It is shown how sets of possibilistic keys can be visualized as possibilistic Armstrong relations, and how they can be discovered from given possibilistic relations. It is also shown how possibilistic keys can be used to clean dirty data by revising the belief in possibility degrees of tuples.
Access provided by Autonomous University of Puebla. Download to read the full chapter text
Chapter PDF
Similar content being viewed by others
Keywords
References
Armstrong, W.W.: Dependency structures of data base relationships. In: IFIP Congress, pp. 580–583 (1974)
Beeri, C., Dowd, M., Fagin, R., Statman, R.: On the structure of Armstrong relations for functional dependencies. J. ACM 31(1), 30–46 (1984)
Benferhat, S., Dubois, D., Prade, H.: Towards a possibilistic logic handling of preferences. Appl. Intell. 14(3), 303–317 (2001)
Beskales, G., Ilyas, I.F., Golab, L.: Sampling the repairs of functional dependency violations under hard constraints. PVLDB 3(1) (2010)
Bistarelli, S., Codognet, P., Rossi, F.: Abstracting soft constraints: Framework, properties, examples. Artif. Intell. 139(2), 175–211 (2002)
Bosc, P., Dubois, D., Prade, H.: Fuzzy functional dependencies – an overview and a critical discussion. In: Proc. of the 3rd IEEE Inter. Conf. on Fuzzy Systems (FUZZ-IEEE 1994), Orlando, FL, June 26-29, pp. 325–330 (1994)
Bosc, P., Pivert, O.: On the impact of regular functional dependencies when moving to a possibilistic database framework. Fuzzy Sets and Systems 140(1), 207–227 (2003)
Calvanese, D., De Giacomo, G., Lenzerini, M.: Keys for free in description logics. In: Baader, F., Sattler, U. (eds.) Proceedings of the 2000 International Workshop on Description Logics (DL 2000), Aachen, Germany, August 17-19. CEUR Workshop Proceedings, vol. 33, pp. 79–88. CEUR-WS.org (2000)
Chu, X., Ilyas, I.F., Papotti, P.: Holistic data cleaning: Putting violations into context. In: Jensen, C.S., Jermaine, C.M., Zhou, X. (eds.) 29th IEEE International Conference on Data Engineering, ICDE 2013, Brisbane, Australia, April 8-12, pp. 458–469. IEEE Computer Society (2013)
Codd, E.F.: A relational model of data for large shared data banks. Commun. ACM 13(6), 377–387 (1970)
Demetrovics, J., Katona, G.O.H.: Extremal combinatorial problems of database models. In: Biskup, J., Demetrovics, J., Paredaens, J., Thalheim, B. (eds.) MFDBS 1987. LNCS, vol. 305, pp. 99–127. Springer, Heidelberg (1988)
Diederich, J., Milton, J.: New methods and fast algorithms for database normalization. ACM Trans. Database Syst. 13(3), 339–365 (1988)
Dubois, D., Lang, J., Prade, H.: Automated reasoning using possibilistic logic: Semantics, belief revision, and variable certainty weights. IEEE Trans. Knowl. Data Eng. 6(1), 64–71 (1994)
Dubois, D., Prade, H.: Epistemic entrenchment and possibilistic logic. Artif. Intell. 50(2), 223–239 (1991)
Dubois, D., Prade, H.: Fuzzy set and possibility theory-based methods in artificial intelligence. Artif. Intell. 148(1-2), 1–9 (2003)
Dubois, D., Prade, H., Schockaert, S.: Stable models in generalized possibilistic logic. In: Brewka, G., Eiter, T., McIlraith, S.A. (eds.) Principles of Knowledge Representation and Reasoning: Proceedings of the Thirteenth International Conference, KR 2012, Rome, Italy, June 10-14. AAAI Press (2012)
Eiter, T., Gottlob, G.: Identifying the minimal transversals of a hypergraph and related problems. SIAM J. Comput. 24(6), 1278–1304 (1995)
Fagin, R.: Horn clauses and database dependencies. J. ACM 29(4), 952–985 (1982)
Gärdenfors, P., Makinson, D.: Nonmonotonic inference based on expectations. Artif. Intell. 65(2), 197–245 (1994)
Geiger, D., Paz, A., Pearl, J.: Axioms and algorithms for inferences involving probabilistic independence. Inf. Comput. 91(1), 128–141 (1991)
Grabisch, M., Prade, H.: The correlation problem in sensor fusion in a possibilistic framework. Int. J. Intell. Syst. 16(11), 1273–1283 (2001)
Grove, A.: Two modellings for theory change. Journal of Philosophical Logic 17(2), 157–170 (1988)
Hartmann, S., Kirchberg, M., Link, S.: Design by example for SQL table definitions with functional dependencies. VLDB J 21(1), 121–144 (2012)
Hartmann, S., Leck, U., Link, S.: On Codd families of keys over incomplete relations. Comput. J. 54(7), 1166–1180 (2011)
Hartmann, S., Link, S.: Efficient reasoning about a robust XML key fragment. ACM Trans. Database Syst. 34(2) (2009)
Hartmann, S., Link, S.: Numerical constraints on XML data. Inf. Comput. 208(5), 521–544 (2010)
Heise, A., Quiane-Ruiz, J.-A., Abedjan, Z., Jentzsch, A., Naumann, F.: Scalable discovery of unique column combinations. PVLDB 7(4), 301–312 (2013)
Jha, A.K., Rastogi, V., Suciu, D.: Query evaluation with soft-key constraints. In: Lenzerini, M., Lembo, D. (eds.) Proceedings of the Twenty-Seventh ACM SIGMOD-SIGACT-SIGART Symposium on Principles of Database Systems, PODS 2008, Vancouver, BC, Canada, June 9-11, pp. 119–128. ACM (2008)
Lutz, C., Areces, C., Horrocks, I., Sattler, U.: Keys, nominals, and concrete domains. J. Artif. Intell. Res. (JAIR) 23, 667–726 (2005)
Mannila, H., Räihä, K.J.: Design by example: An application of Armstrong relations. J. Comput. Syst. Sci. 33(2), 126–141 (1986)
Mannila, H., Räihä, K.J.: Algorithms for inferring functional dependencies from relations. Data Knowl. Eng. 12(1), 83–99 (1994)
Niepert, M., Gyssens, M., Sayrafi, B., Gucht, D.V.: On the conditional independence implication problem: A lattice-theoretic approach. Artif. Intell. 202, 29–51 (2013)
Qi, G., Wang, K.: Conflict-based belief revision operators in possibilistic logic. In: Hoffmann, J., Selman, B. (eds.) Proceedings of the Twenty-Sixth AAAI Conference on Artificial Intelligence, Toronto, Ontario, Canada, July 22-26. AAAI Press (2012)
Sabbadin, R., Fargier, H., Lang, J.: Towards qualitative approaches to multi-stage decision making. Int. J. Approx. Reasoning 19(3-4), 441–471 (1998)
Sarma, A.D., Ullman, J.D., Widom, J.: Schema design for uncertain databases. In: Arenas, M., Bertossi, L.E. (eds.) Proceedings of the 3rd Alberto Mendelzon International Workshop on Foundations of Data Management, Arequipa, Peru, May 12-15. CEUR Workshop Proceedings, vol. 450. CEUR-WS.org (2009)
Shen, Q., Leitch, R.: Fuzzy qualitative simulation. IEEE Transactions on Systems, Man, and Cybernetics 23(4), 1038–1061 (1993)
Suciu, D., Olteanu, D., Ré, C., Koch, C.: Probabilistic Databases. Synthesis Lectures on Data Management. Morgan & Claypool Publishers (2011)
Thalheim, B.: On semantic issues connected with keys in relational databases permitting null values. Elektronische Informationsverarbeitung und Kybernetik 25(1/2), 11–20 (1989)
Toman, D., Weddell, G.E.: On keys and functional dependencies as first-class citizens in description logics. J. Autom. Reasoning 40(2-3), 117–132 (2008)
Zadeh, L.A.: Approximate reasoning based on fuzzy logic. In: Buchanan, B.G. (ed.) Proceedings of the Sixth International Joint Conference on Artificial Intelligence, IJCAI 1979, Tokyo, Japan, August 20-23, vol. 2, pp. 1004–1010. William Kaufmann (1979)
Author information
Authors and Affiliations
Editor information
Editors and Affiliations
Rights and permissions
Copyright information
© 2014 Springer International Publishing Switzerland
About this paper
Cite this paper
Koehler, H., Leck, U., Link, S., Prade, H. (2014). Logical Foundations of Possibilistic Keys. In: Fermé, E., Leite, J. (eds) Logics in Artificial Intelligence. JELIA 2014. Lecture Notes in Computer Science(), vol 8761. Springer, Cham. https://doi.org/10.1007/978-3-319-11558-0_13
Download citation
DOI: https://doi.org/10.1007/978-3-319-11558-0_13
Publisher Name: Springer, Cham
Print ISBN: 978-3-319-11557-3
Online ISBN: 978-3-319-11558-0
eBook Packages: Computer ScienceComputer Science (R0)