Advancement and application of rule-based systems have always been a key research area in computer-aided support for human decision making due to the fact that rule base is one of the most common frameworks for expressing various types of human knowledge in an intelligent system. In this paper, a novel rule-based representation scheme with a belief structure is proposed firstly along with its inference methodology. Such a rule base is designed with belief degrees embedded in the consequent terms as well as in the all antecedent terms of each rule, which is shown to be capable of capturing vagueness, incompleteness, uncertainty, and nonlinear causal relationships in an integrated way. The overall representation and inference framework offers a further improvement and great extension of the recently developed belief rule base inference methodology (refer to as RIMER), although they still share a common scheme at the final step of inference, i.e., the evidential reasoning (ER) approach is applied to the rule combination. It is worth noting that this new extended belief rule base representation is a great extension of traditional rule base as well as fuzzy rule base by encompassing the uncertainty description in the rule antecedent and consequent. Subsequently, a simple but efficient and powerful method for automatically generating such extended belief rule base from numerical data is proposed involving neither time-consuming iterative learning procedure nor complicated rule generation mechanisms but keeping the relatively good performance, which thanks to the new features of the extended rule base with belief structures. Then some case studies in oil pipeline leak detection and software defect detection are provided to illustrate the pro-posed new rule base representation, generation, and inference procedure as well as demonstrate its high performance and efficiency by comparing with some existing approaches.