Motivated by an analogy with matrix decomposition, we introduce the novel problem of relational decomposition. In matrix decomposition, one is given a matrix and has to decompose it as a product of other matrices. In rela- tional decomposition, one is given a relation r and one has to decompose it as a conjunctive query of a particular form q :– q1 ∧ ... ∧ qn. Furthermore, the de- composition has to satisfy certain constraints (e.g. that r ≈ q holds). Relational decomposition is thus the inverse problem of querying as one is given the result of the query and has to compute the relations constituting the query itself.
We show that relational decomposition generalizes several well-studied problems in data mining such as tiling, boolean matrix factorization, and discriminative pat- tern set mining. Furthermore, we provide an initial strategy for solving relational decomposition problems that is based on answer set programming. The result- ing problem formalizations and corresponding solvers fit within the declarative modelling paradigm for data mining.