\n","children":[{"type":"text","text":""}]},{"type":"p","children":[{"type":"text","text":"This paper developed theory and algorithms for semantic query optimization for\nqueries expressible in the \"functional aggregate queries\" format, which includes\na vast number of query classes from database, constraint satisfaction, to\nmachine learning and AI.","italic":true}]},{"type":"p","children":[{"type":"text","text":"Authors: Mahmoud Abo Khamis, Hung Q. Ngo, Atri Rudra. 2016."}]},{"type":"p","children":[{"type":"text","text":"In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of\nDatabase Systems (PODS ‘16). (Best Paper Award, Invited to the Journal of the\nACM)","italic":true}]},{"type":"p","children":[{"type":"text","text":"We define and study the Functional Aggregate Query (FAQ) problem, which\nencompasses many frequently asked questions in constraint satisfaction,\ndatabases, matrix operations, probabilistic graphical models and logic. This is\nour main conceptual contribution. We then present a simple algorithm called\nInsideOut to solve this general problem. InsideOut is a variation of the\ntraditional dynamic programming approach for constraint programming based on\nvariable elimination. Our variation adds a couple of simple twists to basic\nvariable elimination in order to deal with the generality of FAQ, to take full\nadvantage of Grohe and Marx’s fractional edge cover framework, and of the\nanalysis of recent worst-case optimal relational join algorithms."}]},{"type":"p","children":[{"type":"text","text":"Read the PDF:\n"},{"type":"a","url":"https://dl.acm.org/doi/pdf/10.1145/2902251.2902280","title":null,"children":[{"type":"text","text":"Functional Aggregate Query (FAQ): Questions Asked Frequently"}]}]}],"_content_source":{"queryId":"src/content/resources/functional-aggregate-query-faq-questions-asked-frequently.mdx","path":["resource","body"]}},"_content_source":{"queryId":"src/content/resources/functional-aggregate-query-faq-questions-asked-frequently.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":"functional-aggregate-query-faq-questions-asked-frequently.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;
})();
This paper developed theory and algorithms for semantic query optimization for
queries expressible in the "functional aggregate queries" format, which includes
a vast number of query classes from database, constraint satisfaction, to
machine learning and AI.
In Proceedings of the 35th ACM SIGMOD-SIGACT-SIGAI Symposium on Principles of
Database Systems (PODS ‘16). (Best Paper Award, Invited to the Journal of the
ACM)
We define and study the Functional Aggregate Query (FAQ) problem, which
encompasses many frequently asked questions in constraint satisfaction,
databases, matrix operations, probabilistic graphical models and logic. This is
our main conceptual contribution. We then present a simple algorithm called
InsideOut to solve this general problem. InsideOut is a variation of the
traditional dynamic programming approach for constraint programming based on
variable elimination. Our variation adds a couple of simple twists to basic
variable elimination in order to deal with the generality of FAQ, to take full
advantage of Grohe and Marx’s fractional edge cover framework, and of the
analysis of recent worst-case optimal relational join algorithms.