The associations between the items of a test based on the cognitive diagnosis framework and the skills required to solve them are documented in the Q-matrix. If the items have skill profiles that allow for the identification of all possible proficiency classes among examinees, then the Q-matrix of the test is said to be complete. An incomplete Q-matrix causes examinees to be assigned to proficiency classes to which they do not belong. Thus, completeness of the Q-matrix is an integral requirement of any cognitively diagnostic test. However, completeness of the Q-matrix is often difficult to establish, especially, for tests with a large number of items involving multiple skills. As an additional complication, completeness is not an intrinsic property of the Q-matrix, but can only be assessed in reference to a specific diagnostic classification model (DCM) supposed to underlie the data—that is, the Q-matrix of a given test can be complete for one model but incomplete for another. For different types of DCMs, conditions of Q-completeness are studied. Rules are derived to determine the completeness of a given Q-matrix.