Belief Logic Programming (BLP) is a novel form of quantitative logic programming in the presence of uncertain and inconsistent information, which was designed to be able to combine and correlate evidence obtained from non-independent information sources. BLP has non-monotonic semantics based on the concepts of belief combination functions and Dempster-Shafer theory of evidence. Most importantly, unlike the previous efforts to integrate uncertainty and logic programming, BLP can correlate structural information contained in rules and provides more accurate certainty estimates. Declarative semantics is provided as well as query evaluation algorithms. Also BLP is extended to to programs with cycles and to correlated base facts. The results are illustrated via simple, yet realistic examples of rule-based Web service integration.