On Scalable Query Pricing in Data Marketplaces

Query-based pricing enables personalized data acquisition for data buyers, exhibiting potential in data markets. The state-of-the-art SQL query pricing strategy tackles the #P-hard arbitrage-free pricing task with the quadratic computational complexity, far from promptly fulfilling customer demands. In this paper, we propose a novel arbitrage-free and scalable pricing framework ARIA to calculate the prices for various query types in linear time, including select-project-join and simple aggregate (SPJA) queries. For the first time, we model what the query answer tells about the value of each tuple and formulate the tuple-level information of selection, projection, and simple aggregation queries. We develop several price functions based on the total information gain of all tuples. The containing relationship between the query information prevents possible arbitrage arising from query determinacy. We present efficient price computation algorithms to derive the prices of different types of queries with linear time complexity, which scan the common possible value set of tuples one time. In ARIA, the join query is decomposed as multiple single-relation queries for pricing in linear time. Extensive experiments on real and synthetic datasets demonstrate that, ARIA performs 3x faster than the state of the arts while enjoying desirable pricing characteristics.