A number of algebras, calculi, and rule-based query languages have been developed in recent years to meet the challenges of modern applications. Of these, rule-based languages are of interest to researchers in the areas of both databases and logic programming. This paper analyzes the “power” of a certain class of rule-based languages, called value-based languages. By “power” we mean data complexity. The main result of the paper is the establishment of both the upper and lower bounds of the data complexity of the finite versions of three (value-based) logic programming languages: ELPS, COL, and LDL. An interesting consequence of our analysis is a new technique to extend a given total order on a set to its power set using positive rules only (including for built-in predicates).