Affiliations: Department of Mathematics, Statistics and Computer Science, St. Francis Xavier University, PO Box 5000, Antigonish, NS, B2G 2W5, CANADA. e-mail: [email protected]
Note: [] Supported by the Natural Sciences and Engineering Research Council of Canada and by the St. Francis Xavier University Council for Research Address for correspondence: Department of Mathematics, Statistics and Computer Science, St.Francis Xavier University, PO Box 5000, Antigonish, NS, B2G 2W5, CANADA
Abstract: Using a relational approach, we investigate the implication problem for dependencies for information relations, focusing on functional dependencies, association rules and multivalued dependencies. We develop a Rasiowa/Sikorski-style relational calculus and show that the associated tableaux style of reasoning gives a decidable procedure for each of the three kinds of inference problems under consideration. This work has applications to classical database theory and to Rough Set Theory. The techniques may be generalized to the many other data dependencies which have formulations via binary relations and they can be applied to other information relations which arise in the study of incomplete information.
Keywords: information systems, dependencies, relational semantics, relational proof system
