wiki_research

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

query_equivalence_problem (521B)

      1 # Query equivalence problem
      2 
      3 The [decision_problem], given two [queries], of deciding whether they are [query_equivalent]
      4 
      5 Always admits a [reduction] to the [query_containment_problem], because [query_equivalence] can be decided by checking [double_inclusion]
      6 
      7 - [CQ_equivalence_problem] for [CQs]: [NP_complete]
      8 - [UCQ_equivalence_problem] for [UCQs]: [NP_complete]
      9 - [CRPQ_equivalence_problem]
     10 
     11 Up: [database_theory_problem], [query_equivalence]
     12 
     13 See also: [query_containment_problem], [bag_query_equivalence_problem]