Abstract
The paper introduces a model of the Web as an infinite, semi-structured 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 (first-order logic, Datalog, and Datalog with negation) and consider their computational characteristics in terms the notions introduced in this paper. In particular, we are interested in languages or fragments thereof which can be implemented by browsing, or by browsing and searching combined. Surprisingly, stratified and well-founded semantics for negation turn out to have basic shortcomings in this context, while inflationary semantics emerges as an appealing alternative.
Work supported in part by the National Science Foundation under grant number IRI-9221268.
This author's permanent position is INRIA-Rocquencourt, France. His work was supported in part by the Air Force Wright Laboratory Aeronautical Systems Center under ARPA Contract F33615-93-1-1339, and by the Air Force Rome Laboratories under ARPA Contract F30602-95-C-0119
This is a preview of subscription content, log in via an institution to check access.
Preview
Unable to display preview. Download preview PDF.
Similar content being viewed by others
References
S. Abiteboul. Querying semi-structured data. This proceedings.
S. Abiteboul, R. Hull, and V. Vianu. Foundations of Databases. Addison-Wesley, Reading-Massachusetts, 1994.
S. Abiteboul and V. Vianu. Procedural and declarative database update languages. In Proc. ACM PODS, pages 240–250, 1988.
P. Buneman, S. Davidson, and D. Suciu. Programming constructs for unstructured data. In Proc. DBPL, 1995.
[BLCL+94] T. Berners-Lee, R. Cailliau, A. Luotonen, H. Nielsen, and A. Secret. The World-Wide Web. Comm. of the ACM, 37(8):76–82, 1994.
V. Christophides, S. Abiteboul, S. Cluet, and M. Scholl. From structured documents to novel query facilities. In Proc. ACM SIGMOD, pages 313–324, 1994.
A.K. Chandra and D. Harel. Computable queries for relational data bases. Journal of Computer and System Sciences, 21(2):156–178, 1980.
M. P. Consens and A. O. Mendelzon. Expressing structural hypertext queries in graphlog. In Proc. 2nd. ACM Conference on Hypertext, pages 269–292, 1989.
A. Van Gelder. The alternating fixpoint of logic programs with negation. In Proc. ACM PODS, pages 1–11, 1989.
A. Van Gelder, K.A. Ross, and J.S. Schlipf. The well-founded semantics for general logic programs. In Proc. ACM PODS, pages 221–230, 1988.
R. Güting, R. Zicari, and D. M. Choy. An algebra for structured office documents. ACM TOIS, 7(2):123–157, 1989.
D. Harel and T. Hirst. Completeness Results for Recursive Data Bases. In Proc. ACM PODS, pages 244–252, 1993.
P. Kanellakis, G. Kuper, and P. Revesz. Constraint query languages. In Proc. ACM PODS, pages 299–313, 1990.
P. G. Kolaitis and C.H. Papadimitriou. Why not negation by fixpoint? In Proc. ACM PODS, pages 231–239, 1988.
D. Konopnicki and O. Shmueli. W3QS: A query system for the World Wide Web. In Proc. of VLDB'95, pages 54–65, 1995.
V. S. Lakshmanan, F. Sadri, and I. N. Subramanian. A declarative language for querying and restructuring the Web. In Proc. of 6th. International Workshop on Research Issues in Data Engineering, RIDE '96, New Orleans, February 1996.
G. Mihaila, A. Mendelzon, and T. Milo. Querying the World Wide Web. In Proc. PDIS, 1996. Also available in ftp://db.toronto.edu/pdis96.ps.Z.
T. Minohara and R. Watanabe. Queries on structure in hypertext. In Proc. Foundations of Data Organization and Algorithms, pages 394–411, Springer-Verlag, 1993.
A. O. Mendelzon and P. T. Wood. Finding regular simple paths in graph databases. SIAM J. Comp., 24(6), pages 1235–1258, 1995.
D. Quass et al. Querying semistructured heterogeneous information. In Proc. DOOD, pages 319–344, Springer-Verlag, 1995.
Author information
Authors and Affiliations
Editor information
Rights and permissions
Copyright information
© 1996 Springer-Verlag Berlin Heidelberg
About this paper
Cite this paper
Abiteboul, S., Vianu, V. (1996). Queries and computation on the Web. In: Afrati, F., Kolaitis, P. (eds) Database Theory — ICDT '97. ICDT 1997. Lecture Notes in Computer Science, vol 1186. Springer, Berlin, Heidelberg. https://doi.org/10.1007/3-540-62222-5_50
Download citation
DOI: https://doi.org/10.1007/3-540-62222-5_50
Published:
Publisher Name: Springer, Berlin, Heidelberg
Print ISBN: 978-3-540-62222-2
Online ISBN: 978-3-540-49682-3
eBook Packages: Springer Book Archive