The World Wide Web [BLCL

Abstract. The paper introduces a model of the Web as an innite, semistructured set of objects. We reconsider the classical notions of genericity and computability of queries in this new context and relate them to styles of computation prevalent on the Web, based on browsing and searching. We revisit several well-known declarative query languages ( rst-order logic, Datalog, and Datalog with negation) and consider their computational characteristics in terms the notions introduced in this pa-per. In particular, we are interested in languages or fragments thereof which can be implemented by browsing, or by browsing and searching combined. Surprisingly, stratied and well-founded semantics for nega-tion turn out to have basic shortcomings in this context, while in ation-ary semantics emerges as an appealing alternative