\n","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"This paper connects semantic query optimization, physical query optimization &\ncost estimation, to information theory with provable bounds.","italic":true}]},{"type":"p","children":[{"type":"text","text":"Authors: Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu. 2017."}]},{"type":"p","children":[{"type":"text","text":"In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of\nDatabase Systems (PODS ‘17) (Invited to the Journal of the ACM)","italic":true}]},{"type":"p","children":[{"type":"text","text":"Recent works on bounding the output size of a conjunctive query with functional\ndependencies and degree bounds have shown a deep connection between fundamental\nquestions in information theory and database theory. We prove analogous output\nbounds for disjunctive datalog rules, and answer several open questions\nregarding the tightness and looseness of these bounds along the way. The bounds\nare intimately related to Shannon-type information inequalities. We devise the\nnotion of a “proof sequence” of a specific class of Shannon-type information\ninequalities called “Shannon flow inequalities”. We then show how a proof\nsequence can be used as symbolic instructions to guide an algorithm called\nPANDA, which answers disjunctive datalog rules within the size bound predicted.\nWe show that PANDA can be used as a black-box to devise algorithms matching\nprecisely the fractional hypertree width and the submodular width run-times for\naggregate and conjunctive queries with functional dependencies and degree\nbounds."}]},{"type":"p","children":[{"type":"text","text":"Read the PDF:\n"},{"type":"a","url":"https://dl.acm.org/doi/pdf/10.1145/3034786.3056105","title":null,"children":[{"type":"text","text":"What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?"}]}]}],"_content_source":{"queryId":"src/content/resources/what-do-shannon-type-inequalities-submodular-width-and-disjunctive-datalog-have-to-do-with-one.mdx","path":["resource","body"]}},"_content_source":{"queryId":"src/content/resources/what-do-shannon-type-inequalities-submodular-width-and-disjunctive-datalog-have-to-do-with-one.mdx","path":["resource"]}}},"errors":null,"query":"\n query resource($relativePath: String!) {\n resource(relativePath: $relativePath) {\n ... on Document {\n _sys {\n filename\n basename\n breadcrumbs\n path\n relativePath\n extension\n }\n id\n }\n ...ResourceParts\n }\n}\n \n fragment ResourceParts on Resource {\n __typename\n title\n description\n date\n image\n categories\n authors {\n __typename\n name\n link\n }\n seo {\n __typename\n keywords\n description\n image\n image_alt\n canonical_url\n author\n published\n modified\n language\n robots\n site_name\n content_type\n }\n body\n}\n ","variables":{"relativePath":"what-do-shannon-type-inequalities-submodular-width-and-disjunctive-datalog-have-to-do-with-one.mdx"}},"src/content/meta/meta.md":{"data":{"meta":{"_sys":{"filename":"meta","basename":"meta.md","breadcrumbs":["meta"],"path":"src/content/meta/meta.md","relativePath":"meta.md","extension":".md"},"id":"src/content/meta/meta.md","__typename":"Meta","banner":{"__typename":"MetaBanner","enabled":true,"content":{"type":"root","children":[{"type":"p","children":[{"type":"text","text":"Check out "},{"type":"a","url":"/resources/highlights-of-relationalai-at-snowflake-data-cloud-summit-2024","title":"SF summit highlights","children":[{"type":"text","text":"highlights"}]},{"type":"text","text":" of RelationalAI at "},{"type":"text","text":"Snowflake's Data Cloud Summit 2024!","bold":true}]}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","banner","content"]}},"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","banner"]}},"header":{"__typename":"MetaHeader","links":[{"__typename":"MetaHeaderLinks","text":"Product","url":"/product","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",0]}},{"__typename":"MetaHeaderLinks","text":"Company","url":"/company","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",1]}},{"__typename":"MetaHeaderLinks","text":"Docs","url":"/docs","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",2]}},{"__typename":"MetaHeaderLinks","text":"Resources","url":"/resources/all/1","style":"default","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",3]}},{"__typename":"MetaHeaderLinks","text":"Get Started","url":"/get-started","style":"cta","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header","links",4]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","header"]}},"footer":{"__typename":"MetaFooter","sections":[{"__typename":"MetaFooterSections","name":"Product","links":[{"__typename":"MetaFooterSectionsLinks","text":"Overview","url":"/product","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"Use Cases","url":"/product#for-problems-that-matter","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Capabilities","url":"/product#a-new-toolset","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0,"links",2]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",0]}},{"__typename":"MetaFooterSections","name":"Resources","links":[{"__typename":"MetaFooterSectionsLinks","text":"Documentation","url":"/docs/getting_started","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"News","url":"/resources/news/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Research","url":"/resources/research/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",2]}},{"__typename":"MetaFooterSectionsLinks","text":"Releases","url":"/resources/releases/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",3]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1]}},{"__typename":"MetaFooterSections","name":"About Us","links":[{"__typename":"MetaFooterSectionsLinks","text":"Our Company","url":"/company","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",0]}},{"__typename":"MetaFooterSectionsLinks","text":"Contact Us","url":"/get-started","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"Careers","url":"/careers","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",2]}},{"__typename":"MetaFooterSectionsLinks","text":"Legal","url":"/legal","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",3]}},{"__typename":"MetaFooterSectionsLinks","text":"GDPR","url":"/gdpr","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",4]}},{"__typename":"MetaFooterSectionsLinks","text":"Security & Trust","url":"https://trust.relational.ai/","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",5]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2]}}],"socials":[{"__typename":"MetaFooterSocials","text":"GitHub","url":"https://github.com/RelationalAI","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/github.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",0]}},{"__typename":"MetaFooterSocials","text":"LinkedIn","url":"https://www.linkedin.com/company/relationalai/about","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/linkedin.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",1]}},{"__typename":"MetaFooterSocials","text":"Twitter","url":"https://twitter.com/relationalai","icon":"https://assets.tina.io/91d76337-e55d-4722-acb5-3106adb895b6/img/logos/twitter.png","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","socials",2]}}],"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer"]}},"_content_source":{"queryId":"src/content/meta/meta.md","path":["meta"]}}},"errors":null,"query":"\n query meta($relativePath: String!) {\n meta(relativePath: $relativePath) {\n ... on Document {\n _sys {\n filename\n basename\n breadcrumbs\n path\n relativePath\n extension\n }\n id\n }\n ...MetaParts\n }\n}\n \n fragment MetaParts on Meta {\n __typename\n banner {\n __typename\n enabled\n content\n }\n header {\n __typename\n links {\n __typename\n text\n url\n style\n }\n }\n footer {\n __typename\n sections {\n __typename\n name\n links {\n __typename\n text\n url\n }\n }\n socials {\n __typename\n text\n url\n icon\n }\n }\n}\n ","variables":{"relativePath":"./meta.md"}}};
globalThis.tina_info = tina;
})();
What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another? · RelationalAI
Check out highlights of RelationalAI at Snowflake's Data Cloud Summit 2024!
What Do Shannon-type Inequalities, Submodular Width, and Disjunctive Datalog Have to Do with One Another?
This paper connects semantic query optimization, physical query optimization &
cost estimation, to information theory with provable bounds.
Authors: Mahmoud Abo Khamis, Hung Q. Ngo, Dan Suciu. 2017.
In Proceedings of the 36th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of
Database Systems (PODS ‘17) (Invited to the Journal of the ACM)
Recent works on bounding the output size of a conjunctive query with functional
dependencies and degree bounds have shown a deep connection between fundamental
questions in information theory and database theory. We prove analogous output
bounds for disjunctive datalog rules, and answer several open questions
regarding the tightness and looseness of these bounds along the way. The bounds
are intimately related to Shannon-type information inequalities. We devise the
notion of a “proof sequence” of a specific class of Shannon-type information
inequalities called “Shannon flow inequalities”. We then show how a proof
sequence can be used as symbolic instructions to guide an algorithm called
PANDA, which answers disjunctive datalog rules within the size bound predicted.
We show that PANDA can be used as a black-box to devise algorithms matching
precisely the fractional hypertree width and the submodular width run-times for
aggregate and conjunctive queries with functional dependencies and degree
bounds.