{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,8]],"date-time":"2026-04-08T08:52:52Z","timestamp":1775638372908,"version":"3.50.1"},"reference-count":25,"publisher":"Association for Computing Machinery (ACM)","issue":"5","license":[{"start":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T00:00:00Z","timestamp":1446422400000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/100006112","name":"Microsoft","doi-asserted-by":"publisher","id":[{"id":"10.13039\/100006112","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/100000001","name":"National Science Foundation","doi-asserted-by":"publisher","award":["CCF-1047815, IIS-0915054"],"award-info":[{"award-number":["CCF-1047815, IIS-0915054"]}],"id":[{"id":"10.13039\/100000001","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["J. ACM"],"published-print":{"date-parts":[[2015,11,2]]},"abstract":"<jats:p>\n            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 article, 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\n            <jats:italic>query-based pricing<\/jats:italic>\n            . We first identify two important properties that the pricing function must satisfy, the\n            <jats:italic>arbitrage-free<\/jats:italic>\n            and\n            <jats:italic>discount-free<\/jats:italic>\n            properties. Then, we prove that there exists a unique function that satisfies these properties and extends the seller's explicit prices to all queries. Central to our framework is the notion of query determinacy, and in particular\n            <jats:italic>instance-based determinacy<\/jats:italic>\n            : we present several results regarding the complexity and properties of it.\n          <\/jats:p>\n          <jats:p>When both the views and the query are unions of conjunctive queries or conjunctive queries, we show that 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 algorithms with polynomial time data complexity for computing the price of two classes of queries: chain queries (by reducing the problem to network flow), and cyclic queries. Furthermore, we completely characterize the class of conjunctive queries without self-joins that have PTIME data complexity, 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.<\/jats:p>","DOI":"10.1145\/2770870","type":"journal-article","created":{"date-parts":[[2015,11,2]],"date-time":"2015-11-02T17:09:35Z","timestamp":1446484175000},"page":"1-44","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":102,"title":["Query-Based Data Pricing"],"prefix":"10.1145","volume":"62","author":[{"given":"Paraschos","family":"Koutris","sequence":"first","affiliation":[{"name":"University of Washington"}]},{"given":"Prasang","family":"Upadhyaya","sequence":"additional","affiliation":[{"name":"University of Washington"}]},{"given":"Magdalena","family":"Balazinska","sequence":"additional","affiliation":[{"name":"University of Washington"}]},{"given":"Bill","family":"Howe","sequence":"additional","affiliation":[{"name":"University of Washington"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington"}]}],"member":"320","published-online":{"date-parts":[[2015,11,2]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/275487.275516"},{"key":"e_1_2_1_2_1","unstructured":"S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley.   S. Abiteboul R. Hull and V. Vianu. 1995. Foundations of Databases. Addison-Wesley."},{"key":"e_1_2_1_3_1","doi-asserted-by":"crossref","unstructured":"F. N. Afrati. 2007. Rewriting conjunctive queries determined by views. In MFCS. 78--89.   F. N. Afrati. 2007. Rewriting conjunctive queries determined by views. In MFCS. 78--89.","DOI":"10.1007\/978-3-540-74456-6_9"},{"key":"e_1_2_1_4_1","unstructured":"Amazon. Using Amazon S3 Requester Pays with DevPay. docs.amazonwebservices.com\/AmazonDevPay\/latest\/DevPayDeveloperGuide\/index.html?S3RequesterPays.html.  Amazon. Using Amazon S3 Requester Pays with DevPay. docs.amazonwebservices.com\/AmazonDevPay\/latest\/DevPayDeveloperGuide\/index.html?S3RequesterPays.html."},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"M. Balazinska B. Howe and D. Suciu. 2011. Data markets in the cloud: An opportunity for the database community. http:\/\/cloud-data-pricing.cs.washington.edu\/balazinska-pvldb11.pdf.  M. Balazinska B. Howe and D. Suciu. 2011. Data markets in the cloud: An opportunity for the database community. http:\/\/cloud-data-pricing.cs.washington.edu\/balazinska-pvldb11.pdf.","DOI":"10.14778\/3402755.3402801"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/543613.543646"},{"key":"e_1_2_1_7_1","unstructured":"T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms 2nd Ed. MIT Press and McGraw-Hill Book Company.   T. H. Cormen C. E. Leiserson R. L. Rivest and C. Stein. 2001. Introduction to Algorithms 2nd Ed. MIT Press and McGraw-Hill Book Company."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.143"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/1866739.1866758"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1667053.1667055"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00033-8"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1287\/mnsc.48.9.1123.178"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/2213556.2213582"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2367502.2367548"},{"key":"e_1_2_1_15_1","volume-title":"Proceedings of the International Workshop on Web and Databases.","author":"Li C.","unstructured":"C. Li and G. Miklau . 2012. Pricing aggregate queries in a data marketplace . In Proceedings of the International Workshop on Web and Databases. C. Li and G. Miklau. 2012. Pricing aggregate queries in a data marketplace. In Proceedings of the International Workshop on Web and Databases."},{"key":"e_1_2_1_16_1","volume-title":"Elements of Finite Model Theory","author":"Libkin L.","unstructured":"L. Libkin . 2004. Elements of Finite Model Theory . Springer . L. Libkin. 2004. Elements of Finite Model Theory. Springer."},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265534"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.14778\/1880172.1880176"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_5"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1145\/1806907.1806913"},{"key":"e_1_2_1_21_1","volume-title":"Digital Security in a Networked World","author":"Schneier B.","unstructured":"B. Schneier . 2000. Secrets & Lies , Digital Security in a Networked World . John Wiley & Sons . B. Schneier. 2000. Secrets & Lies, Digital Security in a Networked World. John Wiley & Sons."},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1145\/1065167.1065174"},{"key":"e_1_2_1_23_1","first-page":"106","article-title":"Versioning: The smart way to sell information","volume":"76","author":"Shapiro C.","year":"1998","unstructured":"C. Shapiro and H. R. Varian . 1998 . Versioning: The smart way to sell information . Harvard Business Rev. 76 , 106 -- 114 . C. Shapiro and H. R. Varian. 1998. Versioning: The smart way to sell information. Harvard Business Rev. 76, 106--114.","journal-title":"Harvard Business Rev."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780050015"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-30570-5_18"}],"container-title":["Journal of the ACM"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2770870","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2770870","content-type":"application\/pdf","content-version":"vor","intended-application":"syndication"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2770870","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T18:56:12Z","timestamp":1750272972000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2770870"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,11,2]]},"references-count":25,"journal-issue":{"issue":"5","published-print":{"date-parts":[[2015,11,2]]}},"alternative-id":["10.1145\/2770870"],"URL":"https:\/\/doi.org\/10.1145\/2770870","relation":{},"ISSN":["0004-5411","1557-735X"],"issn-type":[{"value":"0004-5411","type":"print"},{"value":"1557-735X","type":"electronic"}],"subject":[],"published":{"date-parts":[[2015,11,2]]},"assertion":[{"value":"2012-10-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-05-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2015-11-02","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}