Datalog Programs over Infinite Databases, Revisited (Extended Abstract)

摘要

This paper's revisit of infinite relational databases, a model traditionally perceived as purely theoretical, was sparked by a concrete implementation setting, and the results obtained here were used in a practical database problem. In the course of implementing a database system for querying Java software, we found that the universe of Java code can be effectively modeled as an infinite database. This modeling makes it possible to distinguish between queries which are "open-ended," that is, whose result may grow as software components are added into the system, and queries which are "closed," in that their result does not change as the software base grows. Further, closed queries can be implemented much more efficiently than open queries. Achievements include an algorithm for distinguishing between these two kinds of queries (we assume that queries are written in Datalog), and an algorithm to generate an efficient evaluation scheme of closed queries, which is a generalization of Vieille's famous QSQR algorithm for top-down evaluation of Datalog programs. A by-product of this work is a rather terse and elegant representation of QSQR.