This paper describes a new domain-independent explanation-based learning (EBL) algorithm that is able to acquire useful new rules in situations where previous EBL algorithms would fail. The new algorithm is complete in the sense that every valid rule that can be extracted from an explanation can be extracted by this algorithm. The new algorithm is described inside a framework that provides insight into how the design of successful EBL systems takes into account operationality and imperfect domain theory issues.