ACM SIGMOD Anthology ACM SIGMOD dblp.uni-trier.de

Cut & Paste.

Paolo Atzeni, Giansalvatore Mecca: Cut & Paste. PODS 1997: 144-153
@inproceedings{DBLP:conf/pods/AtzeniM97,
  author    = {Paolo Atzeni and
               Giansalvatore Mecca},
  title     = {Cut {\&} Paste},
  booktitle = {Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium
               on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona},
  publisher = {ACM Press},
  year      = {1997},
  isbn      = {0-89791-910-6},
  pages     = {144-153},
  ee        = {http://doi.acm.org/10.1145/263661.263678, db/conf/pods/AtzeniM97.html},
  crossref  = {DBLP:conf/pods/97},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}
BibTeX

Abstract

The paper develops EDITOR, a language for manipulating semi-structured documents, such as the ones typically available on the Web. EDITOR programs allow to search and restructure a document. They are based on two simple ideas, taken from text editors: "search" instructions are used to select regions of interest in a document, and "cut & paste" to restructure them. We study the expressive power and the complexity of these programs. We show that they are computationally complete, in the sense that any computable document restructuring can be expressed in EDITOR. We also study the complexity of a safe subclass of programs, showing that it captures exactly the class of polynomial-time restructurings. The language has been implemented in Java, and is used in the ARANEUS project to build database views over Web sites.

Copyright © 1997 by the ACM, Inc., used by permission. Permission to make digital or hard copies is granted provided that copies are not made or distributed for profit or direct commercial advantage, and that copies show this notice on the first page or initial screen of a display along with the full citation.

Load The ACM SIGMOD Anthology, CDROM Edition, Volume 1-3, PODS '82-'98. and ... Load The ACM SIGMOD Anthology, Silver Edition, DVD 1, Proceedings. and ... BibTeX

Printed Edition

Proceedings of the Sixteenth ACM SIGACT-SIGMOD-SIGART Symposium on Principles of Database Systems, May 12-14, 1997, Tucson, Arizona. ACM Press 1997, ISBN 0-89791-910-6
Contents BibTeX

Online Edition: ACM Digital Library

[Index Terms]
[Full Text in PDF Format, 1966 KB]

References

[1]
...
[2]
...
[3]
Serge Abiteboul: Querying Semi-Structured Data. ICDT 1997: 1-18 BibTeX
[4]
Serge Abiteboul, Sophie Cluet, Tova Milo: Querying and Updating the File. VLDB 1993: 73-84 BibTeX
[5]
Serge Abiteboul, Sophie Cluet, Tova Milo: A Database Interface for File Updates. SIGMOD Conference 1995: 386-397 BibTeX
[6]
Serge Abiteboul, Victor Vianu: Queries and Computation on the Web. ICDT 1997: 262-275 BibTeX
[7]
...
[8]
Alfred V. Aho, Margaret J. Corasick: Efficient String Matching: An Aid to Bibliographic Search. Commun. ACM 18(6): 333-340(1975) BibTeX
[9]
...
[10]
Stephen Bellantoni, Stephen A. Cook: A New Recursion-Theoretic Characterization of the Polytime Functions (Extended Abstract). STOC 1992: 283-293 BibTeX
[11]
Tim Berners-Lee, Robert Cailliau, Ari Luotonen, Henrik Frystyk Nielsen, Arthur Secret: The World-Wide Web. Commun. ACM 37(8): 76-82(1994) BibTeX
[12]
G. Elizabeth Blake, Mariano P. Consens, Pekka Kilpeläinen, Per-Åke Larson, T. Snider, Frank Wm. Tompa: Text / Relational Database Management Systems: Harmonizing SQL and SGML. ADB 1994: 267-280 BibTeX
[13]
Peter Buneman, Susan B. Davidson, Gerd G. Hillebrand, Dan Suciu: A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conference 1996: 505-516 BibTeX
[14]
Sudarshan S. Chawathe, Hector Garcia-Molina, Joachim Hammer, Kelly Ireland, Yannis Papakonstantinou, Jeffrey D. Ullman, Jennifer Widom: The TSIMMIS Project: Integration of Heterogeneous Information Sources. IPSJ 1994: 7-18 BibTeX
[15]
Vassilis Christophides, Serge Abiteboul, Sophie Cluet, Michel Scholl: From Structured Documents to Novel Query Facilities. SIGMOD Conference 1994: 313-324 BibTeX
[16]
...
[17]
Charles L. A. Clarke, Gordon V. Cormack, Forbes J. Burkowski: An Algebra for Structured Text Search and a Framework for its Implementation. Comput. J. 38(1): 43-56(1995) BibTeX
[18]
Latha S. Colby, Edward L. Robertson, Lawrence V. Saxton, Dirk Van Gucht: A Query Language for List-Based Complex Objects. PODS 1994: 179-189 BibTeX
[19]
...
[20]
...
[21]
Gaston H. Gonnet: Tutorial: Text Dominated Databases, Theory Practice and Experience. PODS 1994: 301-302 BibTeX
[22]
Gaston H. Gonnet, Frank Wm. Tompa: Mind Your Grammar: a New Approach to Modelling Text. VLDB 1987: 339-346 BibTeX
[23]
...
[24]
Stéphane Grumbach, Tova Milo: An Algebra for Pomsets. ICDT 1995: 191-207 BibTeX
[25]
John E. Hopcroft, Jeffrey D. Ullman: Introduction to Automata Theory, Languages and Computation. Addison-Wesley 1979, ISBN 0-201-02988-X
BibTeX
[26]
...
[27]
David Konopnicki, Oded Shmueli: W3QS: A Query System for the World-Wide Web. VLDB 1995: 54-65 BibTeX
[28]
Laks V. S. Lakshmanan, Fereidoon Sadri, Iyer N. Subramanian: A Declarative Language for Querying and Restructuring the WEB. RIDE-NDS 1996: 12-21 BibTeX
[29]
...
[30]
Arjan Loeffen: Text Databases: A Survey of Text Models and Systems. SIGMOD Record 23(1): 97-106(1994) BibTeX
[31]
Sherry Marcus, V. S. Subrahmanian: Foundations of Multimedia Database Systems. J. ACM 43(3): 474-523(1996) BibTeX
[32]
...
[33]
Giansalvatore Mecca, Anthony J. Bonner: Sequences, Datalog and Transducers. PODS 1995: 23-35 BibTeX
[34]
Alberto O. Mendelzon, George A. Mihaila, Tova Milo: Querying the World Wide Web. PDIS 1996: 80-91 BibTeX
[35]
Alberto O. Mendelzon, Tova Milo: Formal Models of Web Queries. PODS 1997: 134-143 BibTeX
[36]
...
[37]
...
[38]
...

Referenced by

  1. Hasan Davulcu, Guizhen Yang, Michael Kifer, I. V. Ramakrishnan: Computational Aspects of Resilient Data Extraction from Semistructured Sources. PODS 2000: 136-144
  2. David W. Embley, Y. S. Jiang, Yiu-Kai Ng: Record-Boundary Discovery in Web Documents. SIGMOD Conference 1999: 467-478
  3. Stéphane Grumbach, Giansalvatore Mecca: In Search of the Lost Schema. ICDT 1999: 314-331
  4. Seung Jin Lim, Yiu-Kai Ng: WebView: A Tool for Retrieving Internal Structures and Extracting Information from HTML Documents. DASFAA 1999: 71-80
  5. Giansalvatore Mecca, Paolo Atzeni, Alessandro Masci, Paolo Merialdo, Giuseppe Sindoni: The Araneus Web-Base Management System. SIGMOD Conference 1998: 544-546
  6. David W. Embley, Douglas M. Campbell, Y. S. Jiang, Stephen W. Liddle, Yiu-Kai Ng, Dallan Quass, Randy D. Smith: A Conceptual-Modeling Approach to Extracting Data from the Web. ER 1998: 78-91
  7. Giansalvatore Mecca, Alberto O. Mendelzon, Paolo Merialdo: Efficient Queries over Web Views. EDBT 1998: 72-86
  8. Paolo Atzeni, Giansalvatore Mecca, Paolo Merialdo: To Weave the Web. VLDB 1997: 206-215
  9. Paolo Atzeni, Alessandro Masci, Giansalvatore Mecca, Paolo Merialdo, Elena Tabet: ULIXES: Building Relational Views over the Web. ICDE 1997: 576
BibTeX
ACM SIGMOD Anthology - DBLP: [Home | Search: Author, Title | Conferences | Journals]
ACM SIGMOD Anthology: Copyright © by ACM (info@acm.org), Corrections: anthology@acm.org
DBLP: Copyright © by Michael Ley (ley@uni-trier.de), last change: Sat May 16 23:34:17 2009