An Effective Syntax for Bounded Relational Queries
Yang Cao, Wenfei Fan · 2016
A query Q is boundedly evaluable under a set A of access constraints if for all datasets D that satisfy A, there exists a fraction DQ of D such that Q(D) = Q(DQ), and the size of DQ and time for identifying DQ are both independent of the size of D. That is, we can compute Q(D) by accessing a bounded amount of data no matter how big D grows. However, while desirable, it is undecidable to determine whether a query in relational algebra (RA) is bounded under A.