Index Design for Structured Documents Based on Abstraction.

@inproceedings{DBLP:conf/dasfaa/ChowCCX99,
  author    = {Jyh-Herng Chow and
               Josephine M. Cheng and
               Daniel T. Chang and
               Jane Xu},
  editor    = {Arbee L. P. Chen and
               Frederick H. Lochovsky},
  title     = {Index Design for Structured Documents Based on Abstraction},
  booktitle = {Database Systems for Advanced Applications, Proceedings of the
               Sixth International Conference on Database Systems for Advanced
               Applications (DASFAA), April 19-21, Hsinchu, Taiwan},
  publisher = {IEEE Computer Society},
  year      = {1999},
  isbn      = {0-7695-0084-6},
  pages     = {89-96},
  ee        = {db/conf/dasfaa/ChowCCX99.html},
  crossref  = {DBLP:conf/dasfaa/99},
  bibsource = {DBLP, http://dblp.uni-trier.de}
}

Abstract

HTML has been the standard format for delivering information on the web. However, automated information processing on these documents for data exchange and interoperability has been difficult. XML, a subset of SGML, has been proposed to be the next standard format that allows user-defined tags for better describing nested document structures and associated semantics. Operations on structured documents, such as searching in nested document structures, require new functions not currently available on most systems today. We describe a general framework for manipulating structured documents based on document abstractions. An abstraction is an approximation of an actual document, while possessing useful properties for analyses of interest. The framework provides a wide design space for tradeoff between cost and capability. This general framework can be applied to index design, document searching, and categorizations.

We present this framework by focusing on indexing and searching of structured documents in the XML domain, and prove their soundness. We also address the issues of rich data types in XML documents.

Copyright © 1999 by The Institute of Electrical and Electronic Engineers, Inc. (IEEE). Abstract used with permission.

ACM SIGMOD DiSC

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the CD and click on the path of your mount point:
  /Anthology/DISC001 or /cdrom

ACM SIGMOD Anthology

• Windows: Click the letter of your CD drive
  A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
• Mac: Click here
• UNIX/LINUX: mount the DVD and click on the path of your mount point:
  /Anthology/aDVD1 or /dvd

Online Edition: IEEE Computer Society Digital Library

References

[AH87]

Samson Abramsky, Chris Hankin (Eds.): Abstract Interpretation of Declarative Languages. Ellis Horwood 1987, ISBN 0-7458-0109-9
BibTeX

[BCD+]

L. J. Brown, Mariano P. Consens, Ian J. Davis, Christopher R. Palmer, Frank Wm. Tompa: A Structured Text ADT for Object-Relational Databases. TAPOS 4(4): 227-244(1998) BibTeX

[BDHS96]

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

[BK89]

Elisa Bertino, Won Kim: Indexing Techniques for Queries on Nested Objects. IEEE Trans. Knowl. Data Eng. 1(2): 196-214(1989) BibTeX

[Bra97]

...

[CC77]

Patrick Cousot, Radhia Cousot: Abstract Interpretation: A Unified Lattice Model for Static Analysis of Programs by Construction or Approximation of Fixpoints. POPL 1977: 238-252 BibTeX

[CCCX98]

...

[Cho98]

...

[CM94]

Mariano P. Consens, Tova Milo: Optimizing Queries on Files. SIGMOD Conference 1994: 301-312 BibTeX

[DCD98]

...

[FBY92]

William B. Frakes, Ricardo A. Baeza-Yates (Eds.): Information Retrieval: Data Structures & Algorithms. Prentice-Hall 1992, ISBN 0-13-463837-9
Contents BibTeX

[FS98]

Mary F. Fernandez, Dan Suciu: Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998: 14-23 BibTeX

[GW97]

Roy Goldman, Jennifer Widom: DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997: 436-445 BibTeX

[Hoc98]

...

[MAG+97]

Jason McHugh, Serge Abiteboul, Roy Goldman, Dallan Quass, Jennifer Widom: Lore: A Database Management System for Semistructured Data. SIGMOD Record 26(3): 54-66(1997) BibTeX

[MS]

Tova Milo, Dan Suciu: Index Structures for Path Expressions. ICDT 1999: 277-295 BibTeX

[MWA+]

...

[Sch86]

...

[Ver98]

...

[WL97]

Ke Wang, Huiqing Liu: Schema Discovery for Semistructured Data. KDD 1997: 271-274 BibTeX

[XML97]

...

[XML98]

...

[YH93]

Kwangkeun Yi, Williams Ludwell Harrison III: Automatic Generation and Management of Interprocedural Program Analyses. POPL 1993: 246-259 BibTeX

Referenced by

1. Weidong Chen, Jyh-Herng Chow, You-Chin Fuh, Jean Grandbois, Michelle Jou, Nelson Mendonça Mattos, Brian T. Tran, Yun Wang: High Level Indexing of User-Defined Types. VLDB 1999: 554-564