Personal tools
You are here: Home Events Database Seminars Database Seminar: Paris Koutris

Database Seminar: Paris Koutris

— filed under:

Query-based Data Pricing

What
  • Database Seminar
When Mar 22, 2012
from 02:00 PM to 03:00 PM
Where IF 4.31-4.33
Add event to calendar vCal
iCal

Increasingly, data is being bought and sold online, and Web-based marketplace services have emerged to facilitate selling and buying data.  Current pricing mechanisms, however, are very simple, providing a fixed set of views, each with a specific price.  In this paper, we propose a framework for pricing data on the Internet that allows the seller to set explicit prices for only a few views, yet allows the buyer to buy any query; the price of the query is derived automatically from the explicit prices of the views.  We call it ``query-based pricing''.  We first identify two important properties that the pricing function must satisfy, called arbitrage-free and discount-free, then prove that there exists a unique such pricing function that 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 address that, we restrict the explicit prices to be defined only on selection views (which is the common practice today).  We give an algorithm with a PTIME data complexity for computing the price of any chain query, by reducing the problem to a network flow problem.  Furthermore, we completely characterize the class of conjunctive queries without self-joins that have PTIME data complexity (it is slightly larger than chain queries), and prove that all other queries are NP-complete, thus establishing a dichotomy of the complexity of computing the price, when all views are selection queries.

 Joint work with Prasang Upadhyaya, Magdalena Balazinska, Bill Howe and Dan Suciu.

Document Actions