In the analysis of data stored in databases, a very interesting issue is the detection of possible existing relations between attribute values and, at an upper level, relations between attributes themselves. In case uncertainty is present in data, or it is introduced in a pre-processing step, specific data mining and knowledge discovery techniques and methodologies must be provided. The theory of fuzzy subsets is a helpful tool to reach this goal. In this paper we introduce a new definition and an algorithm for computing fuzzy approximate dependencies, a type of relations that can be found between attributes in a fuzzy database, on the basis of a previous definition of fuzzy association rule. We will discuss about possible applications of this new tool.