Derivation digraphs for dependencies in ordinal and similarity-based data

摘要

We present graph-based method of reasoning with if-then rules describing dependencies between attributes in ordinal and similarity-based data. The rules we consider have two basic interpretations as attribute implications in object-attribute incidence data where objects are allowed to have attributes (features) to degrees and as similarity-based functional dependencies in an extension of the Codd model of data. Main results in this paper show that degrees to which if-then rules are semantically entailed from sets (or graded sets) of other if-then rules can be characterized by existence of particular directed acyclic graphs with vertices labeled by attributes and degrees coming from complete residuated lattices. In addition, we show that the construction of directed acyclic graphs can be used to compute closures of sets of attributes and normalized proofs.