Title: Algebraic aspects of attribute dependencies in information systems
Authors: Ivo Düntsch , Dept of Computer Science , Brock University , St Catherines, Ontario, L2S 3A1, Canada
Günther Gediga , Institut für Evaluation und Marktanalysen; Brinkstr. 19; D-49143 Jeggen; Germany
(Equal authorship implied)
Status: Fundamenta Informaticae 29 (1997), 119 - 133
Abstract: Rough set theory has been developed by Pawlak and his co--workers since the early 1980s as a means to handle uncertain or incomplete information. A major tool in the rough set model are indiscernibility relations} - equivalence relations on the universe up to which distinction of objects is possible. Knowledge representation in the model is done via the notion of an information system which, roughly speaking, is like a table in a relational database. A dependency P < Q in an information system is a relation between sets of attributes: If objects agree on all attributes in P, then they agree on all attributes in Q.
In the present paper, we investigate the connections of the dependency relation to the corresponding semilattice of equivalence relations on the object set. The paper is organized as follows: Section 2 introduces our notation and gives the basic definitions and conversions. Section 3 discusses several reductions of information systems, and Section 4 investigates dependency in our algebraic systems. Finally, Section 5 introduces a partial ordering of information systems over a fixed object set which reflects the subsemilattice relation on the set of all equivalence relations on this set.

View technical report version