wiki_research

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

query_relevance (369B)

      1 # Query relevance
      2 
      3 Given a [database] D, a [Boolean_query] Q, and a [fact] f of D, we say that f is *relevant* to Q on D if f belongs to a [minimal_match] of Q in D
      4 
      5 See [bienvenu2026how]
      6 
      7 For [CQs], relevance is [Sigma_P_2_complete] in [combined_complexity]
      8 
      9 For [acyclic_CQs], relevance is [NP_complete] in [combined_complexity]
     10 
     11 Up: [provenance]
     12 
     13 Aliases: relevance