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...

Mô tả đầy đủ

Chi tiết về thư mục
Những tác giả chính: Focke, J, Goldberg, L, Roth, M, Zivny, S
Định dạng: Conference item
Ngôn ngữ:English
Được phát hành: Association for Computing Machinery 2022