wiki_research

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

query_containment (812B)

      1 # Query containment
      2 
      3 For [Boolean_conjunctive_queries], it amounts to [query_evaluation] by [chandra1977optimal]
      4 - via [canonical_query] of a [relational_instance] and [canonical_instance] of a [query]
      5 - this is because [the_following_are_equivalent]:
      6   - A [structure] A has a [homomorphism] to a structure B
      7   - B satisfies the [canonical_query] of A
      8   - the [canonical_query] of B is included in the [canonical_query] of A
      9 
     10 For other [query_languages]:
     11 - [CQs_with_inequalities], cf [jayram2006containment]
     12 - [Datalog_nonrecursive], cf [query_containment_datalog_nonrecursive]
     13 
     14 For other [semirings]:
     15 - [containment_bag_semantics]
     16 - [containment_other_semirings]
     17 
     18 [Computational_problem]: [query_containment_problem]
     19 
     20 Up: [database_theory]
     21 
     22 See also: [CSP], [morvan2025homomorphism]
     23 
     24 Aliases: query contained