{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T13:10:02Z","timestamp":1746277802736,"version":"3.40.4"},"reference-count":48,"publisher":"Association for Computing Machinery (ACM)","issue":"1","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2009,8]]},"abstract":"<jats:p>We propose a database model that allows users to annotate data with<jats:italic>belief statements<\/jats:italic>. Our motivation comes from scientific database applications where a community of users is working together to assemble, revise, and curate a shared data repository. As the community accumulates knowledge and the database content evolves over time, it may contain<jats:italic>conflicting information<\/jats:italic>and members can<jats:italic>disagree<\/jats:italic>on the information it should store. For example, Alice may believe that a tuple should be in the database, whereas Bob disagrees. He may also insert the reason why he thinks Alice believes the tuple should be in the database, and explain what he thinks the correct tuple should be instead.<\/jats:p><jats:p>We propose a formal model for<jats:italic>Belief Databases<\/jats:italic>that interprets users' annotations as belief statements. These annotations can refer both to the base data and to other annotations. We give a formal semantics based on a fragment of multi-agent epistemic logic and define a query language over belief databases. We then prove a key technical result, stating that every belief database can be encoded as a<jats:italic>canonical Kripke structure<\/jats:italic>. We use this structure to describe a relational representation of belief databases, and give an algorithm for translating queries over the belief database into standard relational queries. Finally, we report early experimental results with our prototype implementation on synthetic data.<\/jats:p>","DOI":"10.14778\/1687627.1687629","type":"journal-article","created":{"date-parts":[[2014,6,24]],"date-time":"2014-06-24T12:17:57Z","timestamp":1403612277000},"page":"1-12","source":"Crossref","is-referenced-by-count":21,"title":["Believe it or not"],"prefix":"10.14778","volume":"2","author":[{"given":"Wolfgang","family":"Gatterbauer","sequence":"first","affiliation":[{"name":"University of Washington, Seattle, WA"}]},{"given":"Magdalena","family":"Balazinska","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}]},{"given":"Nodira","family":"Khoussainova","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}]},{"given":"Dan","family":"Suciu","sequence":"additional","affiliation":[{"name":"University of Washington, Seattle, WA"}]}],"member":"320","published-online":{"date-parts":[[2009,8]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"VLDB","author":"Abiteboul S.","year":"1985","unstructured":"S. Abiteboul and G. Grahne . Update semantics for incomplete databases . In VLDB , 1985 . S. Abiteboul and G. Grahne. Update semantics for incomplete databases. In VLDB, 1985."},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247559"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/303976.303983"},{"key":"e_1_2_1_4_1","volume-title":"Report from the SciDB meeting (extremely large database workshop)","author":"Becla J.","year":"2008","unstructured":"J. Becla and K.-T. Lim . Report from the SciDB meeting (extremely large database workshop) , 2008 . J. Becla and K.-T. Lim. Report from the SciDB meeting (extremely large database workshop), 2008."},{"key":"e_1_2_1_5_1","volume-title":"VLDB","author":"Benjelloun O.","year":"2006","unstructured":"O. Benjelloun , A. D. Sarma , A. Y. Halevy , and J. Widom . Uldbs: Databases with uncertainty and lineage . In VLDB , 2006 . O. Benjelloun, A. D. Sarma, A. Y. Halevy, and J. Widom. Uldbs: Databases with uncertainty and lineage. In VLDB, 2006."},{"key":"e_1_2_1_6_1","volume-title":"WebDB","author":"Bernstein P. A.","year":"2002","unstructured":"P. A. Bernstein , F. Giunchiglia , A. Kementsietsidis , J. Mylopoulos , L. Serafini , and I. Zaihrayeu . Data management for peer-to-peer computing: A vision . In WebDB , 2002 . P. A. Bernstein, F. Giunchiglia, A. Kementsietsidis, J. Mylopoulos, L. Serafini, and I. Zaihrayeu. Data management for peer-to-peer computing: A vision. In WebDB, 2002."},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-005-0156-6"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the 2006 UK e-Science all hands meeting","author":"Bose R.","year":"2006","unstructured":"R. Bose , P. Buneman , and D. Ecklund . Annotating scientific data: why it is important and why it is difficult . In Proceedings of the 2006 UK e-Science all hands meeting , 2006 . R. Bose, P. Buneman, and D. Ecklund. Annotating scientific data: why it is important and why it is difficult. In Proceedings of the 2006 UK e-Science all hands meeting, 2006."},{"key":"e_1_2_1_9_1","volume-title":"Annotation in scientific data: A scoping report. Technical report","author":"Buneman P.","year":"2005","unstructured":"P. Buneman , R. Bose , and D. Ecklund . Annotation in scientific data: A scoping report. Technical report , University of Edinburgh , 2005 . P. Buneman, R. Bose, and D. Ecklund. Annotation in scientific data: A scoping report. Technical report, University of Edinburgh, 2005."},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142534"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1007\/11965893_15"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.5555\/645504.656274"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.is.2008.01.007"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066296"},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.1145\/1265530.1265531"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.5555\/647523.728336"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2009.209"},{"key":"e_1_2_1_18_1","volume-title":"CIDR","author":"Eltabakh M. Y.","year":"2007","unstructured":"M. Y. Eltabakh , M. Ouzzani , and W. G. Aref . bdbms - a database management system for biological data . In CIDR , 2007 . M. Y. Eltabakh, M. Ouzzani, and W. G. Aref. bdbms - a database management system for biological data. In CIDR, 2007."},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2008.4497631"},{"key":"e_1_2_1_20_1","doi-asserted-by":"crossref","DOI":"10.7551\/mitpress\/5803.001.0001","volume-title":"Reasoning about knowledge","author":"Fagin R.","year":"1995","unstructured":"R. Fagin , J. Y. Halpern , Y. Moses , and M. Y. Vardi . Reasoning about knowledge . MIT Press , 1995 . R. Fagin, J. Y. Halpern, Y. Moses, and M. Y. Vardi. Reasoning about knowledge. MIT Press, 1995."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1145\/1066157.1066176"},{"key":"e_1_2_1_22_1","first-page":"01","article-title":"Believe it or not: Adding belief annotations to databases. Technical report","volume":"08","author":"Gatterbauer W.","year":"2008","unstructured":"W. Gatterbauer , M. Balazinska , N. Khoussainova , and D. Suciu . Believe it or not: Adding belief annotations to databases. Technical report , UW CSE 08-12 - 01 , Dec. 2008 . http:\/\/db.cs.washington.edu\/beliefDB\/. W. Gatterbauer, M. Balazinska, N. Khoussainova, and D. Suciu. Believe it or not: Adding belief annotations to databases. Technical report, UW CSE 08-12-01, Dec. 2008. http:\/\/db.cs.washington.edu\/beliefDB\/.","journal-title":"UW CSE"},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.5555\/1783534.1783548"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.102"},{"key":"e_1_2_1_25_1","volume-title":"Handbook of Modal Logic","author":"Goranko V.","year":"2006","unstructured":"V. Goranko and M. Otto . Handbook of Modal Logic , chapter Model Theory of Modal Logic. Elsevier , 2006 . V. Goranko and M. Otto. Handbook of Modal Logic, chapter Model Theory of Modal Logic. Elsevier, 2006."},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1093\/logcom\/2.3.397"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247631"},{"issue":"1","key":"e_1_2_1_28_1","first-page":"17","article-title":"Models for incomplete and probabilistic information","volume":"29","author":"Green T. J.","year":"2006","unstructured":"T. J. Green and V. Tannen . Models for incomplete and probabilistic information . IEEE Data Eng. Bull. , 29 ( 1 ): 17 -- 24 , 2006 . T. J. Green and V. Tannen. Models for incomplete and probabilistic information. IEEE Data Eng. Bull., 29(1):17--24, 2006.","journal-title":"IEEE Data Eng. Bull."},{"key":"e_1_2_1_29_1","volume-title":"WebDB","author":"Gribble S. D.","year":"2001","unstructured":"S. D. Gribble , A. Y. Halevy , Z. G. Ives , M. Rodrig , and D. Suciu . What can database do for peer-to-peer ? In WebDB , 2001 . S. D. Gribble, A. Y. Halevy, Z. G. Ives, M. Rodrig, and D. Suciu. What can database do for peer-to-peer? In WebDB, 2001."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2003.1260817"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.1016\/0004-3702(92)90049-4"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1145\/16894.16881"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1145\/1462571.1462577"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/872757.872798"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1137\/0206033"},{"key":"e_1_2_1_36_1","volume-title":"WebDB","author":"Maier D.","year":"1999","unstructured":"D. Maier and L. M. L. Delcambre . Superimposed information for the internet . In WebDB , 1999 . D. Maier and L. M. L. Delcambre. Superimposed information for the internet. In WebDB, 1999."},{"key":"e_1_2_1_37_1","unstructured":"NatureMapping. http:\/\/depts.washington.edu\/natmap\/. NatureMapping. http:\/\/depts.washington.edu\/natmap\/."},{"key":"e_1_2_1_38_1","doi-asserted-by":"publisher","DOI":"10.1093\/jigpal\/jzm059"},{"key":"e_1_2_1_39_1","doi-asserted-by":"publisher","DOI":"10.1145\/1029496.1029525"},{"key":"e_1_2_1_40_1","first-page":"55","volume-title":"Logic and Data Bases","author":"Reiter R.","year":"1977","unstructured":"R. Reiter . On closed world data bases . In Logic and Data Bases , pages 55 -- 76 , 1977 . R. Reiter. On closed world data bases. In Logic and Data Bases, pages 55--76, 1977."},{"key":"e_1_2_1_41_1","volume-title":"A logic for default reasoning. Artif. Intell., 13(1--2):81--132","author":"Reiter R.","year":"1980","unstructured":"R. Reiter . A logic for default reasoning. Artif. Intell., 13(1--2):81--132 , 1980 . R. Reiter. A logic for default reasoning. Artif. Intell., 13(1--2):81--132, 1980."},{"key":"e_1_2_1_42_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2006.174"},{"key":"e_1_2_1_43_1","unstructured":"Sloan Digital Sky Survey. http:\/\/cas.sdss.org. Sloan Digital Sky Survey. http:\/\/cas.sdss.org."},{"key":"e_1_2_1_44_1","doi-asserted-by":"publisher","DOI":"10.1145\/1247480.1247526"},{"key":"e_1_2_1_45_1","doi-asserted-by":"publisher","DOI":"10.1145\/1142473.1142476"},{"key":"e_1_2_1_46_1","unstructured":"UniProt. http:\/\/www.uniprot.org\/. UniProt. http:\/\/www.uniprot.org\/."},{"key":"e_1_2_1_47_1","volume-title":"Logical Approaches to Incomplete Information: A Survey","author":"van der Meyden R.","year":"1998","unstructured":"R. van der Meyden . Logical Approaches to Incomplete Information: A Survey , chapter In Logics for Databases and Information Systems. Kluwer , 1998 . R. van der Meyden. Logical Approaches to Incomplete Information: A Survey, chapter In Logics for Databases and Information Systems. Kluwer, 1998."},{"key":"e_1_2_1_48_1","volume-title":"CIDR","author":"Widom J.","year":"2005","unstructured":"J. Widom . Trio : A system for integrated management of data, accuracy, and lineage . In CIDR , 2005 . J. Widom. Trio: A system for integrated management of data, accuracy, and lineage. In CIDR, 2005."}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/1687627.1687629","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,5,3]],"date-time":"2025-05-03T12:52:02Z","timestamp":1746276722000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/1687627.1687629"}},"subtitle":["adding belief annotations to databases"],"short-title":[],"issued":{"date-parts":[[2009,8]]},"references-count":48,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2009,8]]}},"alternative-id":["10.14778\/1687627.1687629"],"URL":"https:\/\/doi.org\/10.14778\/1687627.1687629","relation":{},"ISSN":["2150-8097"],"issn-type":[{"type":"print","value":"2150-8097"}],"subject":[],"published":{"date-parts":[[2009,8]]}}}