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. Previous work studied pricing mechanisms that compute the price of a query by extending a data seller's explicit prices on certain queries, or investigated the properties that a pricing function should exhibit without detailing a generic construction. In this work, 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. We consider two types of pricing schemes: instance-independent schemes, where the price depends only on the structure of the query, and answer-dependent schemes, where the price also depends on the query output. Our main result is a complete characterization of the structure of pricing functions in both settings, 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. Finally, we discuss various tradeoffs in the design space and present techniques for efficient computation of the proposed pricing functions.
The problem of data pricing has been studied from a wide range of perspectives, including online markets and privacy @cite_14 @cite_7 . @cite_19 examined a variety of issues involved in pricing of information products and presented an economic approach to design of optimal pricing mechanism for online services. @cite_22 introduced the challenge of developing pricing functions in the context of cloud-based environments, where users can pay for queries without buying the entire dataset. This work also outlines various research challenges, such as enabling fine-grained pricing and developing efficient and fair pricing models for cloud-based markets.
@cite_19 @cite_14 @cite_22 @cite_7
2272515049 2168402580 1039000036 2025094765
Data is a commodity. Recent research has considered the mathematical problem of setting prices for different queries over data. Ideal pricing functions need to be flexible --defined for arbitrary queries (select-project-join, aggregate, random sample, and noisy privacy-preserving queries). They should be fine-grained -- a consumer should not be required to buy the entire database to get answers to simple "low-information" queries (such as selecting only a few tuples or aggregating over only one attribute). Similarly, a consumer may not want to pay a large amount of money, only to discover that the database is empty. Finally, pricing functions should satisfy consistency conditions such as being "arbitrage-free" -- consumers should not be able to circumvent the pricing function by deducing the answer to an expensive query from a few cheap queries. Previously proposed pricing functions satisfy some of these criteria (i.e. they are defined for restricted subclasses of queries and or use relaxed conditions for avoiding arbitrage). In this paper, we study arbitrage-free pricing functions defined for arbitrary queries. We propose new necessary conditions for avoiding arbitrage and provide new arbitrage-free pricing functions. We also prove several negative results related to the tension between flexible pricing and avoiding arbitrage, and show how this tension often results in unreasonable prices. Data is increasingly being bought and sold online, and Web-based marketplace services have emerged to facilitate these activities. However, current mechanisms for pricing data are very simple: buyers can choose only from a set of explicit views, each with a specific price. In this paper, we propose a framework for pricing data on the Internet that, given the price of a few views, allows the price of any query to be derived automatically. We call this capability "query-based pricing." We first identify two important properties that the pricing function must satisfy, called arbitrage-free and discount-free. Then, we prove that there exists a unique function that satisfies these properties and extends the seller's explicit prices to all queries. When both the views and the query are Unions of Conjunctive Queries, the complexity of computing the price is high. To ensure tractability, we restrict the explicit prices to be defined only on selection views (which is the common practice today). We give an algorithm with polynomial time data complexity for computing the price of any chain query by reducing the problem to network flow. Furthermore, we completely characterize the class of Conjunctive Queries without self-joins that have PTIME data complexity (this class is slightly larger than chain queries), and prove that pricing all other queries is NP-complete, thus establishing a dichotomy on the complexity of the pricing problem when all views are selection queries. We introduce a new model of user-based dynamic pricing in which decisions occur in real time and are strongly influenced by the budget constraints of users. This model captures the fundamental operation of many electronic markets that are used for allocating resources. In particular, we focus on those used in data centers and cloud computing where pricing is often an internal mechanism used to efficiently allocate virtual machines. We study the allocative properties and dynamic stability of this pricing model under a standard framework of cloud computing systems which leads to highly degenerate systems of prices. We show that as the size of the system grows the user-based budget-constrained dynamic pricing mechanism converges to the standard Walrasian prices. However, for finite systems, the prices can be non-degenerate and the allocations unfair, with large groups of users receiving allocations significantly below their fair share. In addition, we show that improper choice of price update parameters can lead to significant instabilities in prices, which could be problematic in real cloud computing systems, by inducing system instabilities and allowing manipulations by users. We construct scaling rules for parameters that reduce these instabilities. Online information servers that provide access to diverse databases where users can search for, browse through, and download the information they need have been rapidly increasing in number in the past few years. Online vendors have traditionally charged users for information on the based on the length of the time they were connected to the databases. With hardware and software advances, many online servers have recently started changing their pricing strategies to search-based and or subscription-fee pricing. This paper examines the various issues involved in pricing these information products, and presents an economic approach to analyze conditions under which the various pricing schemes may prove optimal for the online servers. Our results show that the variation in consumer expertise and valuation of information affects the choice of a pricing strategy by the server. We present general conditions under which subscription-fee pricing is optimal even when consumer demand is inelastic. We also find that, given the cost structures characterizing the market, undifferentiated online servers can compete and coexist in the market each making positive profits. We show that in a competitive setting an increase in costs of online servers can sometimes benefit them by enabling them to differentiate themselves. Our results offer insights into the trends in pricing strategies and may provide an explanation as to why many servers may persist with connect-time strategies.