The sandbag expressively models uncertainty, imprecision, and varying quality of information about a set. This paper describes an approach to constructing sandbags incrementally from a set of constraints called a fact set. The complexities of fundamental sandbag operations using the fact set approach depend on the application, but are generally intractable. However, by sacri cing optimality, reasonably e cient algorithms can be obtained. This paper describes a data structure and algorithms that produce suboptimal results with polynomial worst case running times in the number of facts. Further, it proves that optimal polynomial algorithms exist for important special cases. It also suggests uses for the sandbag, such as as a general approach to representing sets generated by statistical sampling or as a component of a multimedia DBMS. The goals of this document are to motivate and explain the sandbag, convince the reader that it can be implemented, and to provide su ciently detailed data structures and algorithms that the reader can evaluate them and undertake an implementation of the sandbag.