Safe Web Queries

摘要

This paper explores the fundamental aspects of queries and computation on the Web. We revisit several well-known declarative query languages: CALC~(cυ), Datalog~(cυ), and Datalog~(cυ) with negation and characterize them with respect to (eventual) computability. We also investigate the issue of safety in query languages in the context of the Web, and develop an algorithm for determining safe Web queries that ensure eventual computability. Finally, we show how to identify the fragments in each language implementable by the Web machine.