Datalog  Revival   Serge  Abiteboul   INRIA  Saclay,  Collège  de  France,  ENS  Cachan   5/9/12   1   FO+   Datalog  history   Started  in  77:  logic  and  database  workshop   Simple  idea:  add  recursion  to  posi.ve  FO  queries   Blooming  in  the  80th   ¬   FO   – Logic  programming  was  hot   loop   datalog   datalog¬   Industry  was  not  interested:   – “No  pracNcal  applicaNons  of  recursive  query  theory  …  have  been   found  to  date.”  Hellerstein  and  Stonebraker  (Readings  in  DB  Systems)   Quasi  dead  except  local  resistance  [e.g.,  A.,Go[lob]     Revival    in  this  century   5/9/12   2   OrganizaNon   • • • • • Datalog   Datalog  evaluaNon   Datalog  with  negaNon   Datalog  revival   Conclusion   5/9/12   3   Datalog   5/9/12   4   LimitaNon  of  relaNonal  calculus   G  a  graph:  G(0,1),  G(1,2),  G(2,3),  …  G(10,11)   Is  there  a  path  from  0  to  11    in  the  graph?     0   1   4   5   8   9           10   11   2   3   6   7     k-­‐path  ∃x1…  xk  (  G(0,x1)∧G(x1,x2)∧…∧G(xk-­‐1,xk)  ∧G(xk,11)  )   Path  of  unbounded  length:  infinite  formula     ∨k=1  to  ∞    k-­‐path   5/9/12   5   Term  =  constant  or   variable   Datalog   Datalog  program  =   set  of  datalog  rules   G(2,3)                                        fact   T(x,  y)  ←  G(x,  z),  T(z,  y)          rule     datalog  rule  :  R1(u1)  ←  R2(u2),  .  .  .  ,Rn(un)  for  n  ≥  1       – – – – 5/9/12   head                                              b    ody                             Each  ui  is  a  vector  of  terms     Safe:  each  variable  occurring  in  head  must  occur  in  body     Inten.onal  relaNon:  occurs  in  the  head   Extensional  relaNon:  does  not     6   Datalog  program   1. 2. 3. 4.   G(0,1),  G(1,2),  G(2,3),  …  G(10,11) T(x,  y)  ←  G(x,  y)         T(x,  y)  ←  G(x,  z),  T(z,  y)         Ok()        ←  T(0,  11)   5/9/12    edb(P)  =  {G}      idb(P)    =  {T,Ok}    program  P   7   Datalog  program   1. 2. 3. 4. G(0,1),  G(1,2),  G(2,3),  …  G(10,11)       T(x,  y)  ←  G(x,  y)       T(10,    11)  ←  G   (10,  11)         T(x,  y)  ←  G(x,  z),  T(z,  y)   T(0,   T(9,  11)  ←  G(0,1),   (9,10),   T(1,   T(10,   11)   11)       Ok()        ←  T(0,  11)   Ok()        ←  T(0,  11)       Rule  2:  v(x)=10  &  v(y)  =  11      ☞  T(10,11)   Rule  3:  v(x)=9,  v(z)=10  &  v(y)=11    ☞  T(9,11)   …   Rule  3:  v(x)=0,  v(z)=1  &  v(y)=11    ☞  T(0,11)   Rule  4:  v(x)=0,  v(y)=11      ☞  Ok()     5/9/12   8   Model  semanNcs   View  P  as  a  first-­‐order  sentence  ΣP  describing  the  answer   – Associate  a  formula  to  each  rule      R1(u1)  ←  R2(u2),  .  .  .  ,Rn(un)  :    ∀x1,  .  .  .  ,  xm(  R2(u2)  ∧  .  .  .  ∧  Rn(un)  ⇒R1(u1)  )    where  x1,  .  .  .  ,  xm  are  the  variables  occurring  in  the  rule   P  =  {r1,  ...,  rn},  ΣP  =  r1  ∧  ...  ∧  rn     The  seman.cs  of  P  for  a  database  I,  denoted  P(I),  is  the   minimum  model  of  ΣP  containing  I   Does  it  always  exist?   How  can  it  be  computed?     5/9/12   9   Example:  TransiNve  closure   G(0,1),  G(1,2),  G(2,3)     T(x,y)  ←  G(x,y)   T(x,y)  ←  G(x,z),  T(z,y)   G              P   -­‐-­‐-­‐-­‐        -­‐-­‐-­‐-­‐   0  1        0  1   1  2        1  2                      0  2                                               Does  not   contain  I   5/9/12         G              P   -­‐-­‐-­‐-­‐        -­‐-­‐-­‐-­‐   0  1        0  1   1  2        1  2   2  3        2  3                      0  2                        1  3                         Not  a  model       of  the  formula   G              P   -­‐-­‐-­‐-­‐        -­‐-­‐-­‐-­‐   0  1        0  1   1  2        1  2   2  3        2  3                      0  2                        1  3                        0  3   Minimum  model     containing  I   G                P   -­‐-­‐-­‐-­‐        -­‐-­‐-­‐-­‐   0  1        0  1   1  2        1  2   2  3        2  3                      0  2                        1  3                        0  3                        6  3   Model    but  not   minimal   10   Existence  of  P(I)   There  exists  at  least  one  such  model:  the  largest  instance   one  can  build  with  the  constants  occurring  in  I  and  P  is   a  model  of  P  that  includes  I  –  B(I,P)     P(I)  always  exists:  it  is  the  intersecNon  of  all  models  of  P   that  include  I  over  the  constants  occurring  in  I  and  P     How  can  it  be  computed?   5/9/12   11   Fixpoint  semanNcs   A  fact  A  is  an  immediate  consequence  for  K  and  P  if   1. A  is  an  extensional  fact  in  K,  or     2. for  some  instanNaNon   A  ←  A1,  .  .  .  ,  An  of  a  rule  in  P,   each  Ai  is  in  K   Immediate  consequence  operator:     TP(K)  =  {  immediate  consequences  for  K  and  P  }     Note:  TP  is  monotone      5/9/12   12     Fixpoint  semanNcs  –  conNnued     P(I)  is  a  fixpoint  of  TP  –  That  is:  TP(P(I))⊆  P(I)   Indeed,  P(I)  is  the  least  fixpoint  of  TP  containing  I     Yields  a  means  of  compuNng  P(I)     I  ⊆  TP(I)⊆  TP2(I)⊆  ...  ⊆  Tpi(I)  =  Tpi+1(I)  =  P(I)          ⊆  B(I,P)   5/9/12   13   Proof  theory   • Proof  technique:  SLD  resoluNon   • A  fact  A  is  in  P(I)  iff  there  exists  a  proof  of  A   5/9/12   14   StaNc  analysis   Hard       • Deciding  containment  (P  ⊆  P’)  is  undecidable   • Deciding  equivalence  is  undecidable   • Deciding  boundedness  is  undecidable   – There  exists  k  such  that  for  any  I,  the  fixpoint  converges  in  less  than  k   stages   • So,  op.miza.on  is  hard   5/9/12   15   Datalog  evaluaNon  by  example   5/9/12   16   More  complicated  example:   Reverse  same  generaNon            up        flat        down      a    e      g    f      l    f    a    f      m    n      m    f    f    m      m    o      g    b    g    n      p    m      h    c    h    n            i    d    i    o            p    k    j    o               rsg(x,y)  ←  flat(x,y)       rsg(x,y)  ←  up(x,x1),rsg(y1,x1),down(y1,y)         5/9/12                                   17   rsg(x,y)  ←  flat(x,y)       rsg(x,y)  ←  up(x,x1),rsg(y1,x1),down(y1,y)   f     f   f   l   m   d   f   u   u   a   5/9/12   n   d   u   e    g        f   u   f   rsg   rsg   u   g   u   h   d   b   o   d   c   i   d   d   p   u   j   d   k    m      n    m      o    p        m    a        b    h        f    i          f    j          f      f          k    a        c    a        d   18   Naive  algorithm   Fixpoint   rsg0  =  ∅   rsgi+1  =  flat  ∪  rsgi    ∪  π  16(σ2=4(σ3=5(up  ×  rsgii    ×  down)))   Program   rsg  :=  ∅  ;   repeat    rsg  :=  flat  ∪  rsg  ∪  π16(σ2=4(σ3=5(up  ×  rsg  ×  down)))   unNl  fixpoint       5/9/12   19   Semi-­‐naive   Δ1(x,  y)      ←  flat(x,  y)   Δi+1(x,  y)  ←  up(x,  x1),  Δi(y1,  x1),  down(y1,  y)   Compute  ∪ΔI     Program     – Converges  to  the  answer     – Not  recursive  &  not  a  datalog  program   – SNll  redundant  –  to  avoid  it:   Δi+1(x,  y)  ←  up(x,  x1),  Δi(y1,  x1),  down(y1,  y),  ¬Δi(x,  y)   5/9/12   20   rsg(x,y)  ←  flat(x,y)       rsg(x,y)  ←  up(x,x1),rsg(y1,x1),down(y1,y)   f      g        f   f   l   f   m   d   d   u   e   f   u   u   a   5/9/12   n   u   f   g   d   b   o   u   u   h   d   c   i   d   d   p   u   j   d   k    m      n    m      o    p        m    a        b    h        f    i          f    j          f      f          k    a        c    a        d   21   Δ1   Δ2   Δ3   Semi-­‐naïve  (end)   More  complicated  if  the  rules  are  not  linear   T(x,  y)  ←  G(x,  y)   T(x,  y)  ←  T(x,  z),  T(z,  y)   • Δ1(x,  y)  ←  G(x,  y)   • anc1  :=  Δ1   • • • •   tempi+1(x,  y)  ←  Δi(x,  z),  anci(z,  y)   tempi+1(x,  y)  ←  anci(x,  z),  Δi(z,  y)   Δi+1    :=  tempi+1  -­‐  anci   anci+1  :=  anci  ∪  Δi+1   5/9/12   22   And  beyond   Start  from  a  program  and  a  query   rsg(x,y)  ←  flat(x,y)       rsg(x,y)  ←  up(x,x1),rsg(y1,x1),down(y1,y)   query(y)  ←  rsg(a,  y)   OpNmize  to  avoid  deriving  useless  facts   Two  compeNng  techniques  that  are  roughly  equivalent   – Query-­‐Sub-­‐Query   – Magic  Sets       5/9/12   23   Magic  Set   rsgbf(x,  y)  ←input_rsgbf(x),  flat(x,  y)   rsg{(x,  y)  ←input_rsg[(y),  flat(x,  y)   sup31(x,  x1)  ←input_rsgbf(x),  up(x,  x1)   sup32(x,  y1)  ←sup31(x,  x1),  rsg[(y1,  x1)   rsgbf(x,  y)  ←sup32(x,  y1),  down(y1,  y)   sup41(y,  y1)  ←input_rsg[(y),  down(y1,  y)   sup42(y,  x1)  ←sup41(y,  y1),  rsgbf(y1,  x1)   rsg[(x,  y)  ←sup42(y,  x1),  up(x,  x1)   input_rsgbf(x1)  ←sup31(x,  x1)   input_rsg[(y1)←sup41(y,  y1)   Seed  input_rsgbf(a)  ←   Query  query(y)  ←rsgbf(a,  y)   5/9/12   24   QSQ  at  work   Subqueries     rsg{(y1,e)   rsg{(y1,f)   rsgbf(x,y)     flat(x,y)       sup0(x)      sup1(x,y)   rsgbf(x,y)     up(x,x1),    rsg{(y1,x1),  down(y1,y)       sup0(x)      sup1(x,x1)    sup2(x,y1)      sup3(x,y)   a   a   rsg[(x,y)     flat(x,y)       sup0(y)      sup1(x,y)   a    e   a    f   a      g   a      b   rsg[(x,y)     down(y1,y),  rsgbf(y1,x1),  up(x,x1)     sup0(y)      sup1(y,y1)    sup2(y,x1)      sup3(x,y)   e   g      f   e   f   f   input-­‐rsgbf                                        input-­‐rsg{                              ans-­‐rsgbf                                  ans-­‐rsg{   5/9/12   a   e   f   a      b   g      f   25   SLD-­‐resoluNon  by  example   ←  query(y)                                  query(y)  ←  rsg(a,  y)   ←  rsg(a,y)                              rsg(x,y)  ←  up(x,x1),  rsg(y1,x1),  down(y1,y)   ←  rup(a,x1),  rsg(y1,x1),  down(y1,y)     ←  rsg(y1,f),  down(y1,y)          rsg(x,y)  ←  flat(x,y)     ←  flat(y1,f),  down(y1,y)                                                  flat(g,f)     ←  down(g,y)                                                                                            down(g,b)   ←   5/9/12                        up(a,f)   y=b  is  an  answer   26   Datalog¬  by  example   Accept  negaNve  literal  in  body   Complement  of  transiNve  closure   CompG(x,y)  ←  ¬G(x,y)   5/9/12   27   More  complicated   Some  TP  are  not  monotone     Some  TP  have  no  fixpoint   containing  I   – P1  =  {p  ←    ¬p}   – ∅  →  {p}  →  ∅  →  {p}  →  …     Some  TP  have  several  minimal   fixpoints  containing  I   – P2  =  {p  ←    ¬q,  q  ←    ¬p}   Some  TP  have  a  least  fixpoint  but   sequence  diverges   – P3  =  {p  ←  ¬r  ;  r  ←  ¬p;  p  ←  ¬p,  r}   – alternates  between  ∅  and  {p,  r}   – But  {p}  is  a  least  fixpoint     Model  semanNcs   – Some  programs  have  no  model   containing  I   – Some  program  have  several   minimal  models  containing     – Two  minimal  fixpoints:    {p}  and  {q}.     5/9/12   28   First  fix:  straNficaNon   Impose  condiNon  on  the  syntax   datalog   – StraNfied  programs             Consider  more  complex  semanNcs   ¬   datalog   ¬   ¬   ¬   datalog   datalog   – Many  such  proposals   – Well-­‐founded  semanNcs  based  on  3-­‐valued  logic   5/9/12   29   e,  g  are   loosing   Well-­‐founded  by  example:     2-­‐player  game   move  graph:   (relaNon  K)   c   b   a   e   d   f   g       There  is  a  pebble  in  a  node   2  players  alternate  playing   A  player  moves  the  pebble  following  an  edge   A  player  who  cannot  move  loses   5/9/12   30   d,f  are   winning   Winning  posiNon   move  graph:   (relaNon  K)   c   b   a   e   d   f   g       There  is  a  pebble  in  a  node   2  players  alternate  playing   A  player  moves  the  pebble  following  an  edge   A  player  who  cannot  move  loses   5/9/12   31   a,  b,  c   unknown   No  winner  no  looser   move  graph:   (relaNon  K)   2   c   b   1   1   2   a   e   d   f   g       There  is  a  pebble  in  a  node   2  players  alternate  playing   A  player  moves  the  pebble  following  an  edge   A  player  who  cannot  move  loses   5/9/12   32   Program  to  specify     the  winning/loosing  posiNons   win(x)  ←    move(x,  y),¬win(y)     Well-­‐founded  semanNcs:  find  the  instance  J  that    agrees  with  K  on  move  and      saNsfies  the  formula  corresponding  to  the  rule   Instance  J        –  three-­‐valued  instance    win(d),win(f  )    are  true    win(e),win(g)    are  false    win(a),win(b),win(c)  are  unknown     Fixpoint  semanNcs    based  on  3-­‐valued  logic     5/9/12   33   Fixpoint  computaNon   • win(x)  ←    move(x,  y),¬win(y)   c   e   b   No   maybe   g   a   • • • • • I0:  win  is  always  false   I1:  win:  a,  b,  c,  d,  f   I2:  win:  d,  f   I3:  win:  a,  b,  c,  d,  f   I4:  win:  d,  f     5/9/12   d   yes   f   34   Complexity  and  expressivity   • Datalog  and  Datalog¬  evaluaNons  are    easy   • Datalog⊂  P.me   – – – – In  the  data   Inclusion  in  pNme:  polynomial  number  of  stages;  each  stage  in  pNme   Strict:  Expresses  only  monotone  queries;     But  does  not  even  express  all  PTIME  monotone  queries   • Datalog¬    with  well-­‐founded  seman.cs  =  fixpoint  ⊂  P.me     – In  the  data     – On  ordered  databases,  it  is  exactly  PTIME     5/9/12   35   Datalog  revival   5/9/12   36   Datalog  revival   Datalog  needs  to  be  extended  to  be  useful    Updates,  value  creaNon,  nondeterminism            [e.g.  A.,  Vianu]    Skolem      [e.g.  Go[lob]    Constraints    [e.g.  Revesz]    Time      [e.g.  Chomicki]    DistribuNon    [e.g.  Ac&veXML]    Trees          [e.g.  Ac&veXML]      AggregaNons    [e.g.  Consens  and  Mendelzon]    DelegaNon    [e.g.    Webdamlog]     5/9/12   37   Datalog  revival:  different  domains   DeclaraNve  networking     Data  integraNon  and  exchange   Program  verificaNon       Data  extracNon  from  the  Web   Knowledge  representaNon     ArNfact  and  workflows     Web  data  management     5/9/12    [e.g.    Lou  et  al]    [e.g.    Clio,  Orchestra]    [e.g.    Semmle]    [e.g.    Go[lob,  Lixto]    [e.g.    Go[lob]    [e.g.    AcNveXML]    [e.g.    Webdamlog]        ☚          ☛   38   DeclaraNve  networking   TradiNonal  vs.  declaraNve   Network  state Network  protocol Messages          Distributed  database    Datalog  program    Messages   Series  of  languages/systems  from  Hellerstein  groups  in  Berkeley   – Overlog,  bloom,  dedalus,  bud…   – Performance:  scalability   Many  systems  have  been  developed   Internet  rouNng   Overlay  networks   Sensor  networks   …   5/9/12   39   Data  integraNon   ∀Eid,  Name,  Addr        (  employee(Eid,  Name,  Addr)  ⇒        ∃  Ssn  (  name(Ssn,  Name)  ∧  address(Ssn,  Addr)  )  )     Use  “inverse”  rules  with  Skolem   name(ssn(Name,  Addr),  Name)   address(ssn(Name,  Addr),  Addr)    ←  employee(X,  Name,  Addr)    ←  employee(X,  Name,  Addr)     Possibly  infinite  chase  and    issues  with  terminaNon   5/9/12   40   Program  analysis   Analyze  the  possible  runs  of  a  program   Recursion     Lots  of  possible  runs  –  lots  of  data   – OpNmizaNon  techniques  are  essenNal   – Semi-­‐naïve,  Magic  Sets,  Typed-­‐based  opNmizaNon   5/9/12   41   Data  extracNon   • Georg’s  talk  next   5/9/12   42   Conclusion   5/9/12   43   Issues   Give  precise  semanNcs  to  the  extensions       Some  challenges  for  the  Web   • Scaling  to  large  volumes    Berkeley’s  works   • Datalog  with  distribuNon       Webdamlog    ☛   • Datalog  with  uncertainty       • Datalog  with  inconsistencies   5/9/12   44   Merci ! 5/9/12   45   Georg  Go[lob,     • Professor  at  Oxford  University  &  TU  Wien   • Research:    database,  AI,  logic  and  complexity     • Fellow  of  St  John's  and  Ste  Anne’s  College,   Oxford   • Fellow:    ACM,  ECCAI,  Royal  Society   • Academy:  Austrian,  German,  Europaea   • Program  chair:  IJCAI,  PODS…     • Founder  of  Lixto,  a  company  on  web  data   extracNon   • ERC  Advanced  InvesNgator's  Grant  (DIADEM)     5/9/12   46