Managing Belief Annotations in Databases: A Modal Logic Approach
Explore the concept of belief databases that enable data curation based on modal and default logic in a relational model. The work discusses managing inconsistent views in community databases and presents a motivating application scenario to illustrate the challenges and solutions in handling belief annotations.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
August 25, VLDB 2009 Believe It or Not Adding belief annotations to databases Wolfgang Gatterbauer, Magda Balazinska, Nodira Khoussainova, and Dan Suciu University of Washington http://db.cs.washington.edu/beliefDB/
High-level overview DBMS: manage consistent data Applications need inconsistent DM Scientific databases Internet community databases Community DBMS: manage inconsistent views reason: disagreement ! This work: Belief databases manage data and curation grounded in modal and default logic implemented on top of relational model 2
Agenda Motivating example Logic foundations Relational implementation Discussion 3
Motivating application NatureMapping project (http://depts.washington.edu/natmap/) volunter contribute animal observations one person curates the database problem: does not scale! Observations id uid species date location comment 2 Alice Crow 06-14-08 Lake Placid found feathers Sightings (S) sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Comments (C) cid comment sid c1 found feathers s2 4
1. Distinct database instances S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid Bob D1: Belief worlds: individually consistent, mutually possibly inconsistent 5
1. Distinct database instances S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid Bob Q: Who believes something different than Alice and what? BeliefSQL I: Alice believes that she saw a crow. select U2.name, S1.species, S2.species from Users as U, BELIEF Alice Sightings as S1, BELIEF U.uid Sightings as S2, where S1.sid = S2.sid and S1.species <> S2.species A: {( Bob , Crow , Raven )} insert into BELIEF Alice Sightings values ( s2 , Alice , Crow , 06-14-08 , Lake Placid ) I: Bob believes that she actually saw a raven. insert into BELIEF Bob Sightings values ( s2 , Alice , Raven , 06-14-08 , Lake Placid ) 6
2. Open world assumption S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid Bob S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Carol s2 Alice Raven 06-14-08 Lake Placid Adapted key constraints ! D2: Model incomplete knowledge with exlicit negative beliefs 7
2. Open world assumption I: Carol does not believe that Alice saw a crow nor a raven. S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid insert into BELIEF Carol notSightings values ( s2 , Alice , Crow , 06-14-08 , Lake Placid ) insert into BELIEF Carol notSightings values ( s2 , Alice , Raven , 06-14-08 , Lake Placid ) Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid Bob S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Carol s2 Alice Raven 06-14-08 Lake Placid 8
2. Open world assumption Q: Who disagrees with a sighting from 06-14-08 that Alice believes? select U.name, S1.species S sid uid species date location Users as U, BELIEF Alice Sightings as S1, BELIEF U.uid not Sightings as S2 where S1.sid = S2.sid and and 06-14-08 Lake Placid from s2 Alice Crow Alice location S1.uid = S2.uid S1.species = S2.species S1.date = 06-14-08 S2.date = 06-14-08 S1.location = S2.location S sid uid species date s2 Alice Raven 06-14-08 Lake Placid and and and Bob A: {( Bob , Crow ), ( Carol , Crow )} S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Carol s2 Alice Raven 06-14-08 Lake Placid 9
3. Higher-order beliefs S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid C cid comment sid Bob c1 plain black feathers s2 C cid comment sid Alice Bob c1 purple-black feathers s2 D3: Beliefs about other user s beliefs: allow discussion between users 10
3. Higher-order beliefs I: According to Bob, Alice believes that the S sid uid species date location 06-14-08 Lake Placid feathers of the sighted animal were plain black. insert into BELIEF Bob BELIEF Alice Comments values ( c1 , plain black feathers , s2 ) s2 Alice Crow Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid C cid comment sid Bob c1 plain black feathers s2 C cid comment sid Alice Bob c1 purple-black feathers s2 11
3. Higher-order beliefs Q: Which comments does Alice believe according to Bob, which he does not believe himself? S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid select C1.cid, C1.comment from BELIEF Bob BELIEF Alice Comments as C1, BELIEF Bob not Comments as C2 where C1.cid = C2.cid and and Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid C1.comment = C2.comment C1.sid = C2.sid C cid comment sid Bob A: {( c1 , plain-black feathers )} c1 plain black feathers s2 C cid comment sid Alice Bob c1 purple-black feathers s2 12
3. Higher-order beliefs Q: Which comments does Alice believe according to somebody, which (s)he does not believe themself? S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid select U.name, C1.sid, C1.comment from Users as U, BELIEF U.uid BELIEF Alice Comments as C1, BELIEF U.uid not Comments as C2 Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid where C1.cid = C2.cid and C1.comment = C2.comment and C cid comment sid C1.sid = C2.sid Bob c1 plain black feathers s2 A: {( Bob , c1 , plain-black feathers )} C cid comment sid Alice Bob c1 purple-black feathers s2 13
4. Message board assumption S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid Alice S sid uid species date location s2 Alice Raven 06-14-08 Lake Placid C cid comment sid Bob c1 plain black feathers s2 S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid C cid comment sid Alice Bob c1 purple-black feathers s2 D4: Default assumption: models a trusting attitude & avoids repeated inserts 14
4. Message board assumption Q: Which animal sightings does Alice believe according to Bob, which he does not S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid believe himself? Alice select S1.sid, S1.species from BELIEF Bob BELIEF Alice Sightings as S1, BELIEF Bob not Sightings as S2 S sid uid species date location 06-14-08 Lake Placid where S1.sid = S2.sid and S1.uid = S2.uid and and and s2 Alice Raven C cid comment sid S1.species = S2.species S1.date = S2.date S1.location = S2.location A: {( s2 , Crow )} Bob c1 plain black feathers s2 S sid uid species date location s2 Alice Crow 06-14-08 Lake Placid C cid comment sid Alice Bob c1 purple-black feathers s2 15
What we have seen so far 4 Design decisions for Belief Database model Distinct belief worlds Open world assumption (OWA) Higher-order beliefs Message board assumption BeliefSQL SQL + BELIEF (+ not ) 16
Agenda Motivating example Logic foundations Relational implementation Discussion 17
Logic foundations: Belief statements S sid uid species s2 Alice Crow Bob Alice insert into BELIEF Alice S values ( s2 , Alice , Crow , ) Carol Alice Alice i: Alice S+( s2 , Alice , Crow , ) Alice modal operator & belief path (w) relational tuple (t) sign (s) Bob Alice Bob Carol belief statement = w ts annotation of ground tuple Carol Alice Belief database D = { 1, , n} Bob 18
Logic foundations: Entailment S sid uid species s2 Alice Crow Bob Alice Carol Alice S sid uid species s2 Alice Crow Bob Alice Alice select * from BELIEF Bob BELIEF Alice S Alice Bob Alice Bob Carol One belief annotation: D = { 1} Carol 1= Alice S+( Crow , ) More than one entailed belief: Alice Bob D Bob Alice S+( Crow , ) 19
Logic foundations: Message board assumption Message board assumption Default logic If D w ts and u w ts consistent with D : u u then D u w ts non-monotonic reasoning ! D D \ D Implicit beliefs (assumptions) D Explicit beliefs (annotations) Entailed beliefs (extension) belief database contains more than the explicit belief annotations ! 20
Semi-formal problem statement INPUT OUTPUT Belief statements D ? i1: 1 i2: 2 ... in: n D w1 wdR+(x1, xl) ? q(x) : w Ri+(xi) Adapted key constraints Message board assumption : u u Belief Conjunctive Queries (BCQ) q(x) : w1R1s1(x1), , wgRgsg(xg) 21
Agenda Motivating example Logic foundations Relational implementation Discussion 22
Canonical Kripke structure Belief statements* i1: s11+ i2: Bob s11 i3: Bob s12 i4: Alice s21+ i5: Alice c11+ i6: Bob s22+ i7: Bob Alice c21+ i8: Bob c22+ Carol #1 Alice Carol {s11+,s21+,c11+} Carol #0 Bob #3 Alice Carol {s11+} {s11+,s21+,c11+,c21+} Bob Bob #2 {s11 ,s12 ,s22+,c22+} Message board assumption : i i * Running example from the paper 23
Relational representation Sightings_INTERNAL Sightings_V E tid sid uid species date location wid tid sid s e wid1 uid wid2 s1.1 s1 Carol Bald eagle 06-14-08 Lake Forest #0 s1.1 s1 + y #0 Alice #1 s1.2 s1 Carol Fish eagle 06-14-08 Lake Forest #1 s1.1 s1 + n #0 Bob #2 s2.1 s2 Alice Crow 06-14-08 Lake Placid #1 s2.1 s2 + y #0 Carol #0 s2.2 s2 Alice Raven 06-14-08 Lake Placid #2 s1.1 s1 y #1 Bob #2 #2 s1.2 s1 y #1 Carol #0 Comments_INTERNAL #2 s2.2 s2 + y #2 Alice #3 tid cid comment sid #3 s1.1 s1 + n #2 Carol #0 c1.1 c1 found feathers s2 #3 s2.1 s2 + n #3 Bob #2 c2.1 c2 plain black feathers s2 #3 Carol #0 c2.2 c2 purple-black feathers s2 Comments_V D S wd tid cid s e wid d wid1 wid2 #1 c1.1 c1 + y #0 0 #1 #0 #2 c2.2 c2 + y #1 1 #2 #0 #3 c1.1 c1 + n #2 1 #3 #1 #3 c2.1 c2 + y #3 2 24
Example Translation of a Belief CQ (BCQ) Q: Who disagrees with a sighting from 06-14-08 that Alice believes? BeliefSQL Translation into SQL select into from where and and and E1.uid as uid1, V.tid, V.sid, R.uid, R.species, R.date, R.location, V.s T2 E as E1, Sightings_V as V, Sightings_STAR as R E1.wid1=0 V.wid=E1.wid2 V.tid=R.tid E1.uid='1'; select U.name, S1.species from Users as U, BELIEF Alice Sightings as S1, BELIEF U.uid not Sightings as S2 where S1.sid = S2.sid and S1.uid = S2.uid and S1.species = S2.species and S1.date = 06-14-08 and S2.date = 06-14-08 and S1.location = S2.location select into from where and and E1.uid as uid1, V.tid, V.sid, R.uid, R.species, R.date, R.location, V.s T1 E as E1, Sightings_V as V, Sightings_STAR as R E1.wid1=0 V.wid=E1.wid2 V.tid=R.tid; select from where and and and T1.uid1, T2.species T1 as T1, T2 as T2 T1.sid=T2.sid ((T1.s=0 and T1.uid=T2.uid and T1.species=T2.species and T1.date='6-14-08' and T1.location=T2.location) or (T1.s=1 and (T1.uid<>T2.uid or T1.species<>T2.species or T1.date<>'6-14-08' or T1.location<>T2.location))) T2.s=1 T2.date='6-14-08'; q(x,y) : Alice S+(u,v,y, 06-14-08 ,z), x S (u,v,y, 06-14-08 ,z) drop drop table T2; table T1; 25
Agenda Motivating example Logic foundations Relational implementation Discussion 26
Experiments Size Relative overhead :=|R*| m #users dmax maximum depth of belief annotation = O(mdmax) n In theory: e.g. 100 users, max. depth 2 10,000 21 1,009 Experiments: Size not limitation of semantics, but of relational implementation! Time Depends on type of query (3 types in paper) Q1: ~0.1 s Q2: ~0.4 s Q3: ~4.5 s Experiments on 10,000 annotations ( =22.4): Considerable speed-up to come! 27
Inspirations and related work (excerpt) Annotations Buneman et al. [ICDT 2001 / ICDT 2007] Bhagwat et al. [VLDBJ 2005], Geerts et al. [ICDE 2006] Srivastava & Velegrakis [SIGMOD 2007] Modal logic Fagin et al. [1995] Calvanese et al. [IS 2008] Nguyen [LJ-IGPL 2008] Uncertain / incomplete information Sarma et al. [ICDE 2006] Green & Tannen [IEEE Data Eng. 2006] Dalvi & Suciu [PODS 2007] Inconsistency / key violations Arenas et al. [PODS 1999] Fuxman et al. [SIGMOD 2005] Peer-to-peer computing / collaborative data sharing Bernstein et al. [WebDB 2002] Ives et al. [SIGMOD record 2008] 28
Conclusions Proposed BELIEF databases Goal: manage, curate inconsistent data Implementation Logical foundations Relational translation Current work making it compact and fast 29
BACKUP 30
Relative overhead of relational representation 1E+4 Relative overhed (|R|/n) 1E+3 1E+2 1E+1 1E+1 1E+2 1E+3 1E+4 Distribution of belief path depths (Pr[k=x]) Number of annotations (n) 31
Revisiting the semantics / the user (3) ? BELIEF Alice ( , eagle , ) -> Structured discourse -> Alice ASSERTS ( , eagle , ) (2) BeliefSQL BELIEF Bob BELIEF Alice ( , black feathers , ) Conflicts in belief worlds: OWA, keys, ML, DA -> Bob SUGGESTS that the ASSUMPTION ( , black feathers , ) has led Alice to her original observation (1) SQL Standard relational model 34
