Similarity in relational databases and in information systems theory

• Autorzy: Pomykała J. A.
• Języki publikacji: EN

Abstrakty

EN

The motivation of the paper comes form two sources-theory of relational databases (RDB) and the information systems theory (1ST). On the one hand functional and multivalued dependencies in RDB capture a large portion of the semantics of real world relations, but it has proved useful to consider also other classes of dependencies eg. join or template dependencies. It is known that there is an equivalence between functional dependencies in a relational database and a certain fragment of prepositional logic. This was extended by many authors to include both functional and multivalued dependencies, and complete axiomatizations were given. Also for fully join and for template dependencies complete axioms are known. Dependencies of attributes in information systems theory (1ST) can be expressed in terms of indiscernibility relations derived from the system, in particular data constraints are modeled by them. A generalization of this theory to dependencies in other information frames is an open problem. We propose here an attempt to solve it for frames based on similarity relations. We define dependencies for weak and strong similarity relations with parameters and develop logical formalism for reasoning about them. In RDB theory we propose the notion of "similarity of records", giving the motivations from medicine (eg. similar symptoms should imply similar diagnosis or treatment) and from economy (similar market informations should be followed by similar economic movement or decisions). In consequence we introduced the notions of similarity dependency between sets of attributes in RDB. Examples are shown that the notion introduced is different from functional, multivalued, join and template dependencies in RDB. We analyse Armstrong axioms and Fagin axioms in this context, finding sound (but as yet not necessarily complete) axiomatization of similarity dependency in RDB.

Słowa kluczowe

EN

information systems theory; dependency structures

• Wydawca: De Gruyter
• Czasopismo: Demonstratio Mathematica
• Rocznik: 2002
• Tom: Vol. 35, nr 4
• Strony: 927--953
• Opis fizyczny: Bibliogr. 47 poz.

Twórcy

autor

Pomykała J. A.

• Manager Academy, Society for Trade Initiatives, ul. Kawęczyńska 36, 03-772 Warsaw, Poland

Bibliografia

• [1] W. W. Armstrong, Dependency structures of data base relationships, Information Processing 74.
• [2] C. Beeri, R. Fagin, J. Howard, A complete axiomatization for functional and multivalued dependencies in database relations, Proc. ACM SIG MOD, D. C. P. Smith, ed. New York, NY, 1977, p. 47.
• [3] W. Buszkowski, E. Orłowska, Indiscernibility-Based Formalization of Dependencies in Information Systems, (chapter 9 in [21]).
• [4] P. Ciaccia, M. Patella, P. Zezula, Processing Complex Similarity Queries with Distance - Based Access Methods, in: LNCS 1377, Schek, Saltor, Ramos, Alonso (Eds.), Advances in Database Technology - EDBT'98.
• [5] I. Chajda, B. Zelinka, Tolerance relation on lattices, Casopis pro pestovani matematiky, roc. 99 (1974), Praha.
• [6] E. F. Codd, Further normalisation of the data base relational model, IBM Research Laboratory.
• [7] E. F. Codd, A Relational Model of Data for Large Shared Data Banks, Communications of the ACM, vol. 13, No 6, June 1970.
• [8] Date, Introduction to database systems, (polish translation 1999).
• [9] I. Düntsch, G. Gediga, Rough set data analysis.
• [10] R. Fagin, Multivalued Dependencies and a New Normal Form for Relational Databases, ACM Transactions on Database Systems, Sept. 1977, vol. 2, No 3.
• [11] H. Goszczyńska, personal communication.
• [12] T. B. Iwiński, Algebraic approach to rough sets, Bull. Polish Acad. Sci. Math. 35 (1987).
• [13] J. Järrinen, Knowledge Representation and Rough Sets, Tucs Dissertations, No 14, March 1999.
• [14] B. Konikowska, A logic for Reasoning about Similarity, (chapter 15 in [8]).
• [15] K. Kuratowski, Sur l'opération Ā de l'Analysis Situs, Fund. Math. 3 (1922), 182-199.
• [16] K. Kwast, Reducts on partial database relations, manuscript 13.08.1993.
• [17] T. T. Lee, An Algebraic Theory of Relational Databases, The Bell System Technical Journal vol. 62, No. 10, December 1983.
• [18] W. Mac Caull, A proof System for Dependencies for Information Relations, Fundamenta Informaticae, vol. 42, No 1, April 2000.
• [19] M. Nowotny, Z. Pawlak, Independence of attributes, Bull. Polish Acad. Sci Math. 36, 1988.
• [20] E. Orłowska, Semantics of vague concepts, Foundations of Logic and Linguistics Plenum Press, 1983.
• [21] E. Orłowska, (ed.), Incomplete Information: Rough Set Analysis, Physica-Verlag 2000.
• [22] E. Orłowska, Z. Pawlak, Logical foundations of knowledge representation, ICS PAS Rep. 537, Warszawa 1984.
• [23] K. Otsuka and T. Togawa, A model of cortical neural network structure, 20th Int. Conf. of IEEE Engineering in Medicine and Biology Society, vol. 20, No 4, 1998.
• [24] Z. Pawlak, Information Systems, Theoretical Foundations, Inform. Syst. 6 (1981), 205-218.
• [25] Z. Pawlak, Rough classification, Internat. J. Man-Machine Studies 20 (1984).
• [26] J. A. Pomykała, Approximation Operations in Approximation Space, Bull. Polish Acad. Sci. Math. vol. 35, No. 9-10, 1987.
• [27] J. A. Pomykała, On definability in the nondeterministic information system, Bull. Polish Acad. Sci. Math. vol. 36, No. 3-4, 1988.
• [28] J. A. Pomykała, A remark about the paper of H. Rasiowa and W. Marek, Bull. Pol. Ac. Math., vol. 36, No. 7-8, 1988.
• [29] J. A. Pomykała, Approximation, Similarity and Rough Constructions, ILLC Preparation Series for Computation and Complexity Theory CT-93-07, University of Amsterdam.
• [30] J. A. Pomykała, On similarity based approximation of information, Demonstratio Math.. 27, No. 3-4 (1994), 663-671.
• [31] J. A. Pomykała, On the notion of homomorphism in many-sorted algebras, Demonstratio Math. 36 (2003).
• [32] J. A. Pomykała, E. de Haas, Note on categories of information systems, Demonstratio Math. 27, No. 3-4 (1994), 641-650.
• [33] J. A. Pomykała, J. M. Pomykała, On regularity of hypergraph sequences, Demonstratio Math. 27, No. 3-4 (1994), 651-662.
• [34] H. Rasiowa, W. Marek, Gradual Approximating Sets by Means of Equivalence Relations, Bull. Pol. Ac. Math. vol. 35, 1987.
• [35] C. M. Rauszer, Algebraic Properties of Functional Dependencies, Bull. Pol. Ac. Sc., vol. 33, No 9-10, 1985.
• [36] C. M. Rauszer, An Equivalence between Theory of Functional Dependencies and a Fragment of Intuitionistic logic, Bull. Pol. Ac. Sc., vol. 33, No 9-10, 1985.
• [37] F. S. Roberts, Tolerance Geometry, JSL, vol. XIV, No 1, January 1973.
• [38] Y. Sagiv, C. Delobel, D. Stott Parker Jr., R. Fagin, An Equivalence Between Relational Database Dependencies and a Fragment of Propositional Logic, Journal of the ACM, vol. 28, No. 3, July 1981.
• [39] A. Skowron, C. Rauszer, The Discernibility matrices and functions in Information Systems, (in [40]).
• [40] R. Słowiński (ed.), Intelligent Decision Support, Handbook of Applications and Advances of the Rough Set Theory, Kluwer, 1991.
• [41] A. Tarski, What is elementary geometry, Symposium on the Axiomatic Method.
• [42] T. Traczyk, Common extension of Boolean informational systems, Ann. Soc. Math. Polon. Ser. IV, Fund. Inform. 2 (1978), 63-70.
• [43] J. D. Ullman, Principles of database systems, Computer Science Press, 1980.
• [44] D. Vakarelov, Modal logics for knowledge representation systems, TCS 90, Elsevier (1991), 433-456.
• [45] A. Wiweger, On topological rough sets, Bull. Pol. Ac. Sc. Math., vol. 37, No 1-6, 1989.
• [46] E. C. Zeeman, The Topology of the Brain and Visual Perception, in M. K. Fort, J. R. Ed., Prentice Hall, 1962.
• [47] W. Żakowski, Approximations in the space (U,π), Demonstratio Math. 16 (1983).