Query-based data pricing
Authors:
Open Access
- 21 May 2012
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 167-178
Abstract
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.Keywords
This publication has 13 references indexed in Scilit:
- A firm foundation for private data analysisCommunications of the ACM, 2011
- The complexity of causality and responsibility for query answers and non-answersProceedings of the VLDB Endowment, 2010
- Views and queriesACM Transactions on Database Systems, 2010
- Queries determined by views2007
- Determinacy and Rewriting of Conjunctive Queries Using Views: A Progress ReportLecture Notes in Computer Science, 2006
- Views and queries2005
- Authorization Views and Conditional Query Containment2004
- On the content of materialized aggregate viewsJournal of Computer and System Sciences, 2003
- Pricing of Information Products on Online Servers: Issues, Models, and AnalysisManagement Science, 2002
- Mariposa: a wide-area distributed database systemThe VLDB Journal, 1996