Abstract: Motivated by a growing market that involves buying and selling data over the web, we study pricing schemes that assign value to queries issued over a database. We present a formal framework for pricing queries over data that allows the construction of general families of pricing functions, with the main goal of avoiding arbitrage. Our main result is a complete characterization of the structure of pricing functions, by relating it to properties of a function over a lattice. We use our characterization, together with information-theoretic methods, to construct a variety of arbitrage-free pricing functions, and discuss various tradeoffs in the design space. Finally, we show how our framework can be implemented in practice, and perform query-based data pricing for a large class of SQL queries (including aggregations and join) in real time. This is joint work with Shaleen Deep.