{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,4,2]],"date-time":"2026-04-02T01:02:46Z","timestamp":1775091766103,"version":"3.50.1"},"reference-count":33,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2011,3,1]],"date-time":"2011-03-01T00:00:00Z","timestamp":1298937600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"funder":[{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["226513"],"award-info":[{"award-number":["226513"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]},{"DOI":"10.13039\/501100000781","name":"European Research Council","doi-asserted-by":"publisher","award":["FP7\/2007-2013"],"award-info":[{"award-number":["FP7\/2007-2013"]}],"id":[{"id":"10.13039\/501100000781","id-type":"DOI","asserted-by":"publisher"}]}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["ACM Trans. Database Syst."],"published-print":{"date-parts":[[2011,3]]},"abstract":"<jats:p>Watermarking allows robust and unobtrusive insertion of information in a digital document. During the last few years, techniques have been proposed for watermarking relational databases or Xml documents, where information insertion must preserve a specific measure on data (for example the mean and variance of numerical attributes).<\/jats:p>\n          <jats:p>In this article we investigate the problem of watermarking databases or Xml while preserving a set of parametric queries in a specified language, up to an acceptable distortion. We first show that unrestricted databases can not be watermarked while preserving trivial parametric queries. We then exhibit query languages and classes of structures that allow guaranteed watermarking capacity, namely 1) local query languages on structures with bounded degree Gaifman graph, and 2) monadic second-order queries on trees or treelike structures. We relate these results to an important topic in computational learning theory, the VC-dimension. We finally consider incremental aspects of query-preserving watermarking.<\/jats:p>","DOI":"10.1145\/1929934.1929937","type":"journal-article","created":{"date-parts":[[2011,3,17]],"date-time":"2011-03-17T12:40:16Z","timestamp":1300365616000},"page":"1-24","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":26,"title":["Query-preserving watermarking of relational databases and Xml documents"],"prefix":"10.1145","volume":"36","author":[{"given":"David","family":"Gross-AMBLARD","sequence":"first","affiliation":[{"name":"Le2i CNRS-U Bourgogne, DIJON CEDEX, France and INRIA Saclay, Paris"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2011,3,18]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-003-0097-x"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/76359.76371"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0165-1684(01)00036-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"crossref","unstructured":"Cox I. J. Miller M. L. and Bloom J. A. 2001. Digital Watermarking. Morgan Kaufmann Publishers Inc. San Francisco.   Cox I. J. Miller M. L. and Bloom J. A. 2001. Digital Watermarking. Morgan Kaufmann Publishers Inc. San Francisco.","DOI":"10.1016\/B978-155860714-9\/50009-2"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/602220.602222"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0049-237X(08)71879-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1997.2675"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/343369.343386"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-003-1112-8"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/773153.773172"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/235767.235770"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/502090.502100"},{"key":"e_1_2_1_13_1","volume-title":"Eds","author":"Katzenbeisser S.","year":"2000","unstructured":"Katzenbeisser , S. and Petitcolas , F. A. P. , Eds . 2000 . Information Hiding : Techniques for Steganography and Digital Watermarking. Computer Security Series. Artech House . Katzenbeisser, S. and Petitcolas, F. A. P., Eds. 2000. Information Hiding: Techniques for Steganography and Digital Watermarking. Computer Security Series. Artech House."},{"key":"e_1_2_1_14_1","volume-title":"Proceedings of the Symposium on Discrete Algorithms (SODA). 596--605","author":"Khanna S.","unstructured":"Khanna , S. and Zane , F . 2000. Watermarking maps: Hiding information in structured data . In Proceedings of the Symposium on Discrete Algorithms (SODA). 596--605 . Khanna, S. and Zane, F. 2000. Watermarking maps: Hiding information in structured data. In Proceedings of the Symposium on Discrete Algorithms (SODA). 596--605."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1006\/inco.1994.1100"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190713"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/TDSC.2005.12"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1006\/jcss.1997.1523"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(02)00030-2"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0304-3975(01)00301-2"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/0022-0000(91)90023-X"},{"key":"e_1_2_1_22_1","volume-title":"Proceedings of the 3rd Information Hiding Workshop. 348--367","author":"Qu G.","unstructured":"Qu , G. and Potkonjak , M . 1999. Hiding signatures in graph coloring solutions . In Proceedings of the 3rd Information Hiding Workshop. 348--367 . Qu, G. and Potkonjak, M. 1999. Hiding signatures in graph coloring solutions. In Proceedings of the 3rd Information Hiding Workshop. 348--367."},{"key":"e_1_2_1_23_1","unstructured":"Qu G. and Potkonjak M. 2003. Intellectual Property Protection in VLSI Design: Theory and Practice. Kluwer Publishing.  Qu G. and Potkonjak M. 2003. Intellectual Property Protection in VLSI Design: Theory and Practice. Kluwer Publishing."},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2007.190668"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2004.94"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1145\/800125.804029"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1346330.1346335"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1137\/0208032"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/800057.808710"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/378239.378567"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1109\/TCAD.2003.819900"},{"key":"e_1_2_1_32_1","volume-title":"-Y., Eds","author":"Zeng W.","year":"2006","unstructured":"Zeng , W. , Yu , H. , and Lin , C . -Y., Eds . 2006 . Multimedia Security Technologies for Digital Rights Management. Academic Press . Zeng, W., Yu, H., and Lin, C.-Y., Eds. 2006. Multimedia Security Technologies for Digital Rights Management. Academic Press."},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539795285102"}],"container-title":["ACM Transactions on Database Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929934.1929937","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1929934.1929937","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:32Z","timestamp":1750278392000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1929934.1929937"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2011,3]]},"references-count":33,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2011,3]]}},"alternative-id":["10.1145\/1929934.1929937"],"URL":"https:\/\/doi.org\/10.1145\/1929934.1929937","relation":{},"ISSN":["0362-5915","1557-4644"],"issn-type":[{"value":"0362-5915","type":"print"},{"value":"1557-4644","type":"electronic"}],"subject":[],"published":{"date-parts":[[2011,3]]},"assertion":[{"value":"2009-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2011-03-18","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}