Approximately counting answers to conjunctive queries with disequalities and negations

We study the complexity of approximating the number of answers to a small query φ in a large database D. We establish an exhaustive classification into tractable and intractable cases if φ is a conjunctive query possibly including disequalities and negations: - If there is a constant bound on the ar...

詳細記述

書誌詳細
主要な著者: Focke, J, Goldberg, L, Roth, M, Zivny, S
フォーマット: Conference item
言語:English
出版事項: Association for Computing Machinery 2022