\n","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"The query containment problem is a fundamental algorithmic problem in data\nmanagement. While this problem is well understood under set semantics, it is by\nfar less understood under bag semantics. In this paper we unveil tight\nconnections between information theory and the conjunctive query containment\nunder bag semantics.","italic":true}]},{"type":"p","children":[{"type":"text","text":"Authors: Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, Dan Suciu. 2020."}]},{"type":"p","children":[{"type":"text","text":"In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of\nDatabase Systems (PODS ‘20).","italic":true}]},{"type":"p","children":[{"type":"text","text":"The query containment problem is a fundamental algorithmic problem in data\nmanagement. While this problem is well understood under set semantics, it is by\nfar less understood under bag semantics. In particular, it is a long-standing\nopen question whether or not the conjunctive query containment problem under bag\nsemantics is decidable.We unveil tight connections between information theory\nand the conjunctive query containment under bag semantics.These connections are\nestablished using information inequalities, which are considered to be the laws\nof information theory. Our first main result asserts that deciding the validity\nof a generalization of information inequalities is many-one equivalent to the\nrestricted case of conjunctive query containment in which the containing query\nis acyclic; thus, either both these problems are decidable or both are\nundecidable. Our second main result identifies a new decidable case of the\nconjunctive query containment problem under bag semantics. Specifically, we give\nan exponential-time algorithm for conjunctive query containment under bag\nsemantics, provided the containing query is chordal and admits a simple junction\ntree."}]},{"type":"p","children":[{"type":"text","text":"Read the PDF:\n"},{"type":"a","url":"https://arxiv.org/pdf/1906.09727.pdf","title":null,"children":[{"type":"text","text":"Bag Query Containment and Information Theory"}]}]}],"_content_source":{"queryId":"src/content/resources/bag-query-containment-and-information-theory.mdx","path":["resource","body"]}},"_content_source":{"queryId":"src/content/resources/bag-query-containment-and-information-theory.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":"bag-query-containment-and-information-theory.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/getting_started","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":"Blog","url":"/resources/all/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",1]}},{"__typename":"MetaFooterSectionsLinks","text":"News","url":"/resources/news/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",2]}},{"__typename":"MetaFooterSectionsLinks","text":"Research","url":"/resources/research/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",3]}},{"__typename":"MetaFooterSectionsLinks","text":"Releases","url":"/resources/releases/1","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",1,"links",4]}}],"_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":"Security & Trust","url":"https://trust.relational.ai/","_content_source":{"queryId":"src/content/meta/meta.md","path":["meta","footer","sections",2,"links",4]}}],"_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;
})();
Bag Query Containment and Information Theory · RelationalAI
Check out highlights of RelationalAI at Snowflake's Data Cloud Summit 2024!
The query containment problem is a fundamental algorithmic problem in data
management. While this problem is well understood under set semantics, it is by
far less understood under bag semantics. In this paper we unveil tight
connections between information theory and the conjunctive query containment
under bag semantics.
Authors: Mahmoud Abo Khamis, Phokion G. Kolaitis, Hung Q. Ngo, Dan Suciu. 2020.
In Proceedings of the 39th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of
Database Systems (PODS ‘20).
The query containment problem is a fundamental algorithmic problem in data
management. While this problem is well understood under set semantics, it is by
far less understood under bag semantics. In particular, it is a long-standing
open question whether or not the conjunctive query containment problem under bag
semantics is decidable.We unveil tight connections between information theory
and the conjunctive query containment under bag semantics.These connections are
established using information inequalities, which are considered to be the laws
of information theory. Our first main result asserts that deciding the validity
of a generalization of information inequalities is many-one equivalent to the
restricted case of conjunctive query containment in which the containing query
is acyclic; thus, either both these problems are decidable or both are
undecidable. Our second main result identifies a new decidable case of the
conjunctive query containment problem under bag semantics. Specifically, we give
an exponential-time algorithm for conjunctive query containment under bag
semantics, provided the containing query is chordal and admits a simple junction
tree.