Queries and computation on the web

The paper introduces a model of the Web as an infinite, semistructured set of objects. We reconsider the classical notions of genericity and computabi lity of queries in this new context and relate them to styles of computatio n prevalent on the Web, based on browsing and searching. We revisit several well-known declarative query languages (first-order logic, Datalog, and Da talog with negation) and consider their computational characteristics in te rms of the notions introduced in this paper. In particular, we are interest ed in languages or fragments thereof which can be implemented by browsing, or by browsing and searching combined. Surprisingly, stratified and well-fo unded semantics for negation turn out to have basic shortcomings in this co ntext, while inflationary semantics emerges as an appealing alternative. (C ) 2000 Elsevier Science B.V. All rights reserved.