wiki_research

personal research wiki
git clone https://a3nm.net/git/wiki_research/
Log | Files | Refs

provenance_membership_testing (579B)

      1 # Provenance membership testing
      2 
      3 Studied in [calautti2023complexity], for [Datalog]
      4 
      5 - Fix a [query] Q
      6 - Input:
      7   - A [database] D
      8   - Optionally: A [query_answer] t
      9   - A subdatabase D' of D
     10 - Output: Decide if D' is in the provenance (optionally: of t) of Q on D.
     11 
     12 This is [provenance_operational] not [provenance_definitional], so for instance in [Datalog] it depends on the set of [proof_trees]
     13 
     14 Results in [calautti2023complexity]:
     15 
     16 Also: [calautti2024complexity] on computing minimal sets, and also testing when the multiplicity is given as input
     17 
     18 Up: [provenance_datalog]