Digital Symposium Collection 2000  

 
 
 
 
 
 

 


















Type Inference for Queries on Semistructured Data

Tova Milo and Dan Suciu

  View Paper (PDF)  

Return to Semistructured Data

Abstract
We study the problem of type checking and type inference for queries over semistructured data. Introducing a novel traces technique, we show that the problem is difficult in general (NP-complete), but can be solved in PTIME for many practical cases, including, in particular, queries over XML data. Besides being interesting by itself, we show that type inference and the related traces technique have several important applications, facilitating query formulation, optimization, and verification.


References

Note: References link to DBLP on the Web.

[AV97]
Serge Abiteboul , Victor Vianu : Regular Path Queries with Constraints. PODS 1997 : 122-133
[BDFS97]
Peter Buneman , Susan B. Davidson , Mary F. Fernandez , Dan Suciu : Adding Structure to Unstructured Data. ICDT 1997 : 336-350
[BDHS96]
Peter Buneman , Susan B. Davidson , Gerd G. Hillebrand , Dan Suciu : A Query Language and Optimization Techniques for Unstructured Data. SIGMOD Conf. 1996 : 505-516
[BM99]
Catriel Beeri , Tova Milo : Schemas for Integration and Translation of Structured and Semi-structured Data. ICDT 1999 : 296-313
[CDSS97]
Sophie Cluet , Claude Delobel , Jérôme Siméon , Katarzyna Smaga : Your Mediators Need Data Conversion! SIGMOD Conference 1998 : 177-188
[DFF+9u]
...
[DGM98]
Diego Calvanese , Giuseppe De Giacomo , Maurizio Lenzerini : What can Knowledge Representation do for Semi-Structured Data? AAAI/IAAI 1998 : 205-210
[FFK+98]
Mary F. Fernandez , Daniela Florescu , Jaewoo Kang , Alon Y. Levy , Dan Suciu : Catching the Boat with Strudel: Experiences with a Web-Site Management System. SIGMOD Conference 1998 : 414-425
[FS98]
Mary F. Fernandez , Dan Suciu : Optimizing Regular Path Expressions Using Graph Schemas. ICDE 1998 : 14-23
[Gol90]
...
[GW97]
Roy Goldman , Jennifer Widom : DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases. VLDB 1997 : 436-445
[Mit90]
...
[Mit96]
...
[MMM96]
Alberto O. Mendelzon , George A. Mihaila , Tova Milo : Querying the World Wide Web. PDIS 1996 : 80-91
[MZ98]
Tova Milo , Sagit Zohar : Using Schema Matching to Simplify Heterogeneous Data Translation. VLDB 1998 : 122-133
[NAM97]
Svetlozar Nestorov , Serge Abiteboul , Rajeev Motwani : Infering Structure in Semistructured Data. SIGMOD Record 26(4) : 39-43(1997)
[PAGM96]
Yannis Papakonstantinou , Serge Abiteboul , Hector Garcia-Molina : Object Fusion in Mediator Systems. VLDB 1996 : 413-424
[PGMW95]
Yannis Papakonstantinou , Hector Garcia-Molina , Jennifer Widom : Object Exchange Across Heterogeneous Information Sources. ICDE 1995 : 251-260
[QRS+95]
Dallan Quass , Anand Rajaraman , Yehoshua Sagiv , Jeffrey D. Ullman , Jennifer Widom : Querying Semistructured Heterogeneous Information. DOOD 1995 : 319-344
[Var82]
Moshe Y. Vardi : The Complexity of Relational Query Languages (Extended Abstract). STOC 1982 : 137-146

Referenced by

  1. Serge Abiteboul , Bernd Amann , Sophie Cluet , Adi Eyal , Laurent Mignet , Tova Milo : Active Views for Electronic Commerce. VLDB 1999 : 138-149

BIBTEX

@inproceedings{DBLP:conf/pods/MiloS99,
  author    = {Tova Milo and
                Dan Suciu},
   title     = {Type Inference for Queries on Semistructured Data},
   booktitle = {Proceedings of the Eighteenth ACM SIGACT-SIGMOD-SIGART Symposium
                on Principles of Database Systems, May 31 - June 2, 1999, Philadelphia,
                Pennsylvania},
   publisher = {ACM Press},
   year      = {1999},
   isbn      = {1-58113-062-7},
   pages     = {215-226},
   crossref  = {DBLP:conf/pods/99},
   bibsource = {DBLP, http://dblp.uni-trier.de} } },


























Copyright(C) 2000 ACM