Managing Belief Annotations in Databases: A Modal Logic Approach

 
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/
 
August 25, VLDB 2009
2
High-level overview
 
•
DBMS: manage consistent data
•
Applications need inconsistent DM
–
Scientific databases
–
Internet community databases
•
Community DBMS: manage inconsistent views
 
•
This work: 
Belief databases
–
manage data and curation
–
grounded in modal and default logic
–
implemented on top of relational model
reason: disagreement !
 
3
 
Agenda
 
•
Motivating example
•
Logic foundations
•
Relational implementation
•
Discussion
4
Motivating application
•
NatureMapping project 
(http://depts.washington.edu/natmap/)
–
volunter contribute animal observations
–
one person curates the database
 
problem: does not scale!
Alice
Bob
5
1. Distinct database instances
D1: Belief worlds: 
individually consistent, 
mutually possibly inconsistent
Alice
Bob
6
1. Distinct database instances
BeliefSQL
insert
 
into 
BELIEF 
‘Alice’
 
Sightings
values
 
(‘s2’,‘Alice’,‘Crow’,’06-14-08’,‘Lake Placid’)
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
 
Q: Who believes something different
than Alice and what?
 
A: {(‘Bob’, ‘Crow’, ‘Raven’)}
I: Alice believes that she saw a crow.
insert
 
into 
BELIEF 
‘Bob’ 
Sightings
values
 
(‘s2’,‘Alice’,‘Raven’,’06-14-08’,‘Lake Placid’)
 
I: Bob believes that she actually saw a raven.
Alice
Bob
7
2. Open world assumption
Carol
 
−
 
−
D2: Model incomplete knowledge with exlicit negative beliefs
Adapted key constraints !
Alice
Bob
8
2. Open world assumption
Carol
−
−
I: Carol does not believe that Alice saw a crow 
nor a raven.
insert
 
into 
BELIEF 
‘Carol’ not
 
Sightings
values
 
(‘s2’,‘Alice’,‘Crow’,’06-14-08’,‘Lake Placid’)
insert
 
into 
BELIEF 
‘Carol’ not
 
Sightings
values
 
(‘s2’,‘Alice’,‘Raven’,’06-14-08’,‘Lake Placid’)
Alice
Bob
9
2. Open world assumption
Carol
−
−
Q: Who disagrees with a sighting from 
‘06-14-08’ that Alice believes?
 
A: {(‘Bob’, ‘Crow’), (‘Carol’, ‘Crow’)}
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
 
Bob
 
Alice
Alice
Bob
10
3. Higher-order beliefs
D3: Beliefs about other user’s beliefs: allow discussion between users
Bob
Alice
Alice
Bob
11
3. Higher-order beliefs
I: According to Bob, Alice believes that the
feathers of the sighted animal were plain black.
insert
 
into 
BELIEF 
‘Bob’ 
BELIEF 
‘Alice’ 
Comments
values
 
(‘c1’, ‘plain black feathers’, ‘s2’)
Bob
Alice
Alice
Bob
12
3. Higher-order beliefs
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
 
C1.comment = C2.comment
and
 
C1.sid = C2.sid
Q: Which comments does Alice believe according
to Bob, which he does not believe himself?
 
A: {(‘c1’,‘plain-black feathers’)}
 
Bob
 
Alice
 
Alice
 
Bob
 
13
 
3. Higher-order beliefs
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
where
 
C1.cid = C2.cid
and
 
C1.comment = C2.comment
and
 
C1.sid = C2.sid
 
Q: Which comments does Alice believe according
to somebody, which (s)he does not believe themself?
 
A: {(‘Bob’, ‘c1’, ‘plain-black feathers’)}
Bob
Alice
Alice
Bob
14
4. Message board assumption
D4: Default assumption: models a trusting attitude & avoids repeated inserts
 
15
 
4. Message board assumption
 
Alice
 
Bob
 
Bob
 
Alice
 
Q: Which animal sightings does Alice believe
according to Bob, which he does not
believe himself?
select
 
S1.sid, S1.species
from
 
BELIEF 
‘Bob’ 
BELIEF 
‘Alice’ 
Sightings as S1,
 
BELIEF 
‘Bob’ not 
Sightings as S2
where
 
S1.sid = S2.sid
and
 
S1.uid = S2.uid
and
 
S1.species = S2.species
and
 
S1.date = S2.date
and
 
S1.location = S2.location
 
A: {(‘s2’, ‘Crow’)}
16
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’)
 
17
 
Agenda
 
•
Motivating example
•
Logic foundations
•
Relational implementation
•
Discussion
 
Bob
Alice
Bob
18
Logic foundations: Belief statements
Carol
Alice
Carol
insert
 
into 
BELIEF 
‘Alice’ 
S
values
 
(‘s2’, ‘Alice’, ‘Crow’,…)
i: 
☐
Alice
 S
+
(‘s2’,‘Alice’,‘Crow’,…)
belief statement
 = 
☐
w
 t
s
relational tuple (t)
sign (s)
modal operator
& belief path (w)
Bob
Carol
Alice
Bob
…
…
…
…
…
…
Alice
ε
Belief database D = 
{
1
, …, 
n
}
Alice
 
Alice
“annotation of
  ground tuple”
19
Logic foundations: Entailment
Carol
Carol
Alice
Bob
Carol
Alice
Bob
…
…
…
…
…
ε
 
1
=
☐
Alice
 S
+
(…‘Crow’,…)
Bob
Alice
Bob
Alice
…
Alice
select
 
*
from
 
BELIEF 
‘Bob’ 
BELIEF 
‘Alice’ 
S
Bob
Alice
Alice
One belief annotation:
More than one entailed belief:
 
D = {
1
}
20
Logic foundations: Message board assumption
Message board assumption
 
and 
☐
u
w
 
t
s 
consistent with D
 
 : 
☐
u
 
 
☐
u
 
Default logic
 
D
Explicit beliefs
(annotations)
 
D
Entailed beliefs
(extension)
 
D \ D
Implicit beliefs
(assumptions)
non-monotonic reasoning !
belief database “contains” more than the explicit belief annotations !
21
“Semi-formal” problem statement
i
1
: 
1
i
2
: 
2
...
i
n
: 
n
 
Belief statements
 
Message board
assumption
INPUT
OUTPUT
 
Adapted
key constraints
 
Belief Conjunctive Queries (BCQ)
 
22
 
Agenda
 
•
Motivating example
•
Logic foundations
•
Relational implementation
•
Discussion
{
s1
1
−
,s1
2
−
,
s2
2
+
,
c2
2
+
}
{
s1
1
+
,s2
1
+
,
c1
1
+
,
c2
1
+
}
{s1
1
+
}
{s1
1
+
,s2
1
+
,
c1
1
+
}
23
Canonical Kripke structure
i
1
: 
s1
1
+
i
2
: 
☐
Bob 
s1
1
−
i
3
: 
☐
Bob
 s1
2
−
i
4
: 
☐
Alice
 s2
1
+
i
5
: 
☐
Alice
 c1
1
+
i
6
: 
☐
Bob
 s2
2
+
i
7
: 
☐
Bob
Alice
 c2
1
+
i
8
: 
☐
Bob
 c2
2
+
Belief statements*
Message board 
assumption
Alice
Bob
Bob
Carol
Bob
Carol
Alice
 
#1
 
#0
 
#2
* Running example from the paper
Carol
Carol
 
#3
24
Relational representation
25
Example Translation of a Belief CQ (BCQ)
 
BeliefSQL
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
Q: Who disagrees with a sighting from ’06-14-08’ that Alice believes?
select 
 
E1.uid as uid1, V.tid, V.sid, R.uid, R.species, R.date, R.location, V.s
into 
 
T2
from 
 
E as E1, Sightings_V as V, Sightings_STAR as R
where 
 
E1.wid1=0
and 
 
V.wid=E1.wid2
and 
 
V.tid=R.tid
and 
 
E1.uid='1';
 
select 
 
E1.uid as uid1, V.tid, V.sid, R.uid, R.species, R.date, R.location, V.s
into 
 
T1
from 
 
E as E1, Sightings_V as V, Sightings_STAR as R
where 
 
E1.wid1=0
and 
 
V.wid=E1.wid2
and 
 
V.tid=R.tid;
 
select 
 
T1.uid1, T2.species
from 
 
T1 as T1, T2 as T2
where 
 
T1.sid=T2.sid
and 
 
((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)))
and 
 
T2.s=1
and 
 
T2.date='6-14-08';
 
drop 
 
table T2;
drop 
 
table T1;
 
Translation into SQL
q(x,y) :−
 
☐
Alice
 S
+
(u,v,y,
‘
06-14-08’,z),
              
 
☐
x
 S
−
(u,v,y,‘06-14-08’,z)
 
26
 
Agenda
 
•
Motivating example
•
Logic foundations
•
Relational implementation
•
Discussion
27
Experiments
ρ = O(m
d
max
)
 
m     … #users
 
d
max
 … maximum
     depth of
belief
     annotation
 
In theory: e.g. 100 users, max. depth 2
 
Experiments:
 
ρ 
 
10,000
 
ρ 
 
21 – 1,009
Size not limitation of semantics, but of relational implementation!
Size
Time
 
Depends on type of query (3 types in paper)
 
Experiments on 10,000 annotati
ons (ρ =22.4)
:
Considerable speed-up to come!
 
Q1: ~0.1 s
Q2: ~0.4 s
Q3: ~4.5 s
 
28
 
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]
 
29
 
Conclusions
 
•
Proposed BELIEF databases
–
Goal: manage, curate inconsistent data
 
•
Implementation
–
Logical foundations
–
Relational translation
 
•
Current work
–
making it compact and fast
 
30
 
BACKUP
 
31
 
Relative overhead of relational representation
 
32
 
Query types and execution times
 
33
 
Belief Conjunctive Queries (BCQ)
34
Revisiting the semantics / the user
 
BELIEF ’Alice’ (…,’eagle’,…)
-> ’Alice’ASSERTS (…,’eagle’,…)
 
BELIEF ’Bob’ BELIEF  ’Alice’
(…,’black feathers’,…)
 
-> ’Bob’SUGGESTS that the ASSUMPTION
(…,’black feathers’,…) has led ‘Alice’ to her
original observation
Standard relational model
Conflicts in belief worlds:
OWA, keys, ML, DA
 
-
> Structured discourse
(1) SQL
(2) BeliefSQL
 
(3) ?

								

								

								

										

												
Slide Note

												
 

										

								


								
						

							
						


							

								

									
										
Embed
									
									
										
Share
									

									
									
									

								

								
							


							

							 
 							 
 							 
						  


							
							

								
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.


								
    
																		
  •   Belief Databases
    • 
																	
  •    Modal Logic
    • 
																	
  •    Data Curation
    • 
																	
  •    Relational Model
    • 
																	
  •    Community Databases
    • 
																

								

								

									

										atinn
										

											 atinn Follow
											

										

									

									
Uploaded on Sep 11, 2024 | 0 Views

								

								


								

									
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

								

								
  1. 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/
    2. 
            
            
            
  2. 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
    3. 
            
            
            
  3. Agenda     Motivating example     Logic foundations      Relational implementation     Discussion 3
    4. 
            
            
            
  4. 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
    5. 
            
            
            
  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 D1: Belief worlds: individually consistent,  mutually possibly inconsistent 5
    6. 
            
            
            
  6. 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
    7. 
            
            
            
  7. 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
    8. 
            
            
            
  8. 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
    9. 
            
            
            
  9. 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
    10. 
            
            
            
  10. 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
    11. 
            
            
            
  11. 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
    12. 
            
            
            
  12. 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
    13. 
            
            
            
  13. 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
    14. 
            
            
            
  14. 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
    15. 
            
            
            
  15. 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
    16. 
            
            
            
  16. 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
    17. 
            
            
            
  17. Agenda     Motivating example     Logic foundations      Relational implementation     Discussion 17
    18. 
            
            
            
  18. 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
    19. 
            
            
            
  19. 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
    20. 
            
            
            
  20. 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
    21. 
            
            
            
  21. 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
    22. 
            
            
            
  22. Agenda     Motivating example     Logic foundations      Relational implementation     Discussion 22
    23. 
            
            
            
  23. 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
    24. 
            
            
            
  24. 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
    25. 
            
            
            
  25. 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
    26. 
            
            
            
  26. Agenda     Motivating example     Logic foundations      Relational implementation     Discussion 26
    27. 
            
            
            
  27. 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
    28. 
            
            
            
  28. 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
    29. 
            
            
            
  29. Conclusions     Proposed BELIEF databases     Goal: manage, curate inconsistent data     Implementation     Logical foundations     Relational translation     Current work     making it compact and fast 29
    30. 
            
            
            
  30. BACKUP 30
    31. 
            
            
            
  31. 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
    32. 
            
            
            
  32. Query types and execution times 32
    33. 
            
            
            
  33. Belief Conjunctive Queries (BCQ) 33
    34. 
            
            
            
  34. 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
    35. 
            
            
            
							

							

					

					
					
					

						
Related

						

						


							
							
							
							

						

							

									

      

        
          

            

              MAKING RECOMMENDATIONS
            

            

              
MAKING RECOMMENDATIONS

              
safa

            

          

        
      


     

      

        
          

            

              Logic Families
            

            

              
Logic Families

              
eilonwy

            

          

        
      


     

      

        
          

            

              Databases and Database Applications
            

            

              
Databases and Database Applications

              
lilymay

            

          

        
      


     

      

        
          

            

              Exploring the World of Bioinformatics Databases
            

            

              
Exploring the World of Bioinformatics Databases

              
milan

            

          

        
      


     

      

        
          

            

              Modal Verbs in English
            

            

              
Modal Verbs in English

              
philippa

            

          

        
      


     

      

        
          

            

              Logic Circuits in Aircraft Systems
            

            

              
Logic Circuits in Aircraft Systems

              
ailani

            

          

        
      


     

      

        
          

            

              Modal Verbs: Epistemic and Deontic Uses
            

            

              
Modal Verbs: Epistemic and Deontic Uses

              
romi

            

          

        
      


     

      

        
          

            

              Relational Databases and File-Based Systems
            

            

              
Relational Databases and File-Based Systems

              
kaori

            

          

        
      


     

      

        
          

            

              Modal Verbs in English Grammar
            

            

              
Modal Verbs in English Grammar

              
jubal

            

          

        
      


     

      

        
          

            

              Modal Verbs Exercise - Can and Can't Practice Activities
            

            

              
Modal Verbs Exercise - Can and Can't Practice Activities

              
rohan

            

          

        
      


     

      

        
          

            

              Propositional Logic and Mathematical Logic in Computer Science
            

            

              
Propositional Logic and Mathematical Logic in Computer Science

              
leov452

            

          

        
      


     

      

        
          

            

              Overview of Sacred Music: Plainchant, Gregorian Chant, and Modal Music
            

            

              
Overview of Sacred Music: Plainchant, Gregorian Chant, and Modal Music

              
najm_15

            

          

        
      


     

      

        
          

            

              Modal Verbs for Ability, Obligation, Prohibition, and Advice
            

            

              
Modal Verbs for Ability, Obligation, Prohibition, and Advice

              
harp_595

            

          

        
      


     

      

        
          

            

              Introduction to Symbolic Logic: Understanding Logical Inferences
            

            

              
Introduction to Symbolic Logic: Understanding Logical Inferences

              
ais_m

            

          

        
      


     

      

        
          

            

              Modal Verbs in Grammar - Mega Goals 6 Unit 1 Everyone Makes Mistakes
            

            

              
Modal Verbs in Grammar - Mega Goals 6 Unit 1 Everyone Makes Mistakes

              
jrye

            

          

        
      


     

      

        
          

            

              Modal Testing and Analysis in Structural Dynamics
            

            

              
Modal Testing and Analysis in Structural Dynamics

              
ayrabel

            

          

        
      


     

      

        
          

            

              Modal Verbs: Usage and Examples
            

            

              
Modal Verbs: Usage and Examples

              
thulb

            

          

        
      


     

      

        
          

            

              Modal Verbs in English
            

            

              
Modal Verbs in English

              
jonath

            

          

        
      


     

      

        
          

            

              Propositional and Notional Attitudes in Logic and Natural Language Processing
            

            

              
Propositional and Notional Attitudes in Logic and Natural Language Processing

              
sood_lyn

            

          

        
      


     

      

        
          

            

              Digital Logic Circuits and Design Principles
            

            

              
Digital Logic Circuits and Design Principles

              
joy_mo

            

          

        
      


     

      

        
          

            

              Introduction to Digital Electronic Circuits and Logic Gates
            

            

              
Introduction to Digital Electronic Circuits and Logic Gates

              
innleyw

            

          

        
      


     

      

        
          

            

              Deep Dive into Driver Annotations: Part II
            

            

              
Deep Dive into Driver Annotations: Part II

              
russ_byn

            

          

        
      


     							

						

					

					

				


				

			

		
		

			

				
				

					
More Related Content

					

						

														

					

				

				
			

		












 





  
  
  



giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#giItT1WQy@!-/#