文章基本信息

标题：ENUMERATING ANSWERS TO FIRST-ORDER QUERIES OVER DATABASES OF LOW DEGREE
本地全文：下载
作者：Arnaud Durand ; Nicole Schweikardt ; Luc Segoufin 等
期刊名称：Logical Methods in Computer Science
印刷版ISSN：1860-5974
电子版ISSN：1860-5974
出版年度：2022
卷号：18
期号：2
页码：1-23
DOI：10.46298/lmcs-18(2:7)2022
语种：English
出版社：Technical University of Braunschweig
摘要：A class of relational databases has low degree if for all $\delta>0$, all but finitely many databases in the class have degree at most $n^{\delta}$, where $n$ is the size of the database. Typical examples are databases of bounded degree or of degree bounded by $\log n$. It is known that over a class of databases having low degree, first-order boolean queries can be checked in pseudo-linear time, i.e.\ for all $\epsilon>0$ in time bounded by $n^{1+\epsilon}$. We generalize this result by considering query evaluation. We show that counting the number of answers to a query can be done in pseudo-linear time and that after a pseudo-linear time preprocessing we can test in constant time whether a given tuple is a solution to a query or enumerate the answers to a query with constant delay.
关键词：Enumeration;First-Order;Low degree