Uncovering functional dependencies in MDD-compiled product catalogues

A functional dependency is a logical relationship amongst the attributes that define a table of data. Specifically, a functional dependency holds when the values of a subset of the attributes in a dataset determine the values of one or more other attributes. Uncovering such dependencies is utilized in many domains, such as database design. We demonstrate that it can also be utilized in a recommendation context when datasets represent product catalogues. State-of-the-art approaches to discovering functional dependencies require a tabular representation of the data. However, product catalogues can sometimes be defined implicitly, for example, as a set of solutions to a combinatorial problem. Such combinatorial catalogues can have a very large number of products, thus making standard approaches to uncovering functional dependencies inapplicable. In this paper we present the first approach to computing functional dependencies over compiled knowledge representations which can often be small even for huge catalogues. In particular, we develop efficient algorithms that operate over decision diagrams, which allow us to handle catalogues that are out of reach for current approaches. We apply our algorithms to tabular and combinatorial benchmarks and detect a number of properties that could be considered as anomalies in product catalogues.