wiki_research

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

datalog_query_evaluation (760B)

      1 # Datalog query evaluation
      2 
      3 [datalog_query_evaluation_algorithms]
      4 
      5 [computational_complexity]:
      6 - [exptime_complete] in [combined_complexity], cf [gottlob2012datalog]
      7   - already [exptime_hard] with
      8     - empty input [database]
      9     - one single [datalog_rule]
     10     - two-element universe
     11 - for [datalog_linear]:
     12   - [pspace_complete]
     13   - already [pspace_hard] with the following, cf [gottlob2023complexity]
     14     - empty input [database]
     15     - one single [datalog_rule]
     16     - two-element universe
     17 
     18 An important idea is to run the [CQs] of the [rule_bodies] efficiently: [conjunctive_query_optimization] / [optimal_joins]
     19 
     20 [zhang2023enhancing]: [query_evaluation] of [datalog] via [hypertreewidth]
     21 
     22 Up: [datalog], [query_evaluation]
     23 
     24 See also: [query_optimization]