  Implicational bases (IBs) are a common representation of finite closure
systems and lattices, along with meet-irreducible elements. They appear in a
wide variety of fields ranging from logic and databases to Knowledge Space
Theory. Different IBs can represent the same closure system. Therefore, several
IBs have been studied, such as the canonical and canonical direct bases. In
this paper, we investigate the $D$-base, a refinement of the canonical direct
base. It is connected with the $D$-relation, an essential tool in the study of
free lattices. The $D$-base demonstrates desirable algorithmic properties, and
together with the $D$-relation, it conveys essential properties of the
underlying closure system. Hence, computing the $D$-base and the $D$-relation
of a closure system from another representation is crucial to enjoy its
benefits. However, complexity results for this task are lacking. In this paper,
we give algorithms and hardness results for the computation of the $D$-base and
$D$-relation. Specifically, we establish the $NP$-completeness of finding the
$D$-relation from an arbitrary IB; we give an output-quasi-polynomial time
algorithm to compute the $D$-base from meet-irreducible elements; and we obtain
a polynomial-delay algorithm computing the $D$-base from an arbitrary IB. These
results complete the picture regarding the complexity of identifying the
$D$-base and $D$-relation of a closure system.
