Database I, année 2023

Plan

  1. Graphs and relations
    • modeling graphs with relational algebra
    • Property testing: checking that a graph is a line, a transitive closure
    • Querying: finding triangles
    • Connected?
  2. First order logic over finite models: a definition
    • Syntax
    • Semantic
    • Theorem: first order logic captures relational algebras computations
  3. Inexpressibility results
    • Ehrenfeucht–Fraïssé games
    • Inexpressibility of graph Connectivity.

Compiled the: sam. 10 févr. 2024 16:29:26 CET