Managing highly correlated semi-structured data: architectural aspects of a digital archive

ABSTRACT

XML techniques are well suited to describe, manage, store, and exchange hierarchical, semi-structured data. Information represented beyond hierarchical structures can still be described and exchanged in XML format employing additional concepts such as ID/IDREF or XLink. However, retrieval, manipulation, and storage mechanisms are far away from being the ideal solution for such data. Query languages do not perform efficiently in these cases. Especially in scenarios, such as the Digital Wossidlo Archive (WossiDiA), a project dealing with a huge number of arbitrarily correlated data units, XML query evaluation and retrieval techniques face problems, such as intricate querying and bad efficiency. At this point a solution to manage these data efficiently needs to be devised. This paper introduces a first approach which attempts to find such a solution for the WossiDiA information system.

REFERENCES

• 1: C. Beeri and Y. Tzaban. SAL: An Algebra for Semistructured Data in XML. WebDB (Informal Proceedings)pages 37--42, 1999.
• 2: E. Behrends, O. Fritzen, and W. May. Handling Interlinked XML Instances on the Web. In EDBT pages 792--810, 2006.
• 3: Andreas Brandstädt , Van Bang Le , Jeremy P. Spinrad, Graph classes: a survey, Society for Industrial and Applied Mathematics, Philadelphia, PA, 1999
• 4: T. Bray, J. Paoli, C. M. Sperberg-McQueen, E. Maler, and F. Yergeau. Extensible Markup Language (XML) 1.0 (Fourth Edition). Technical report,W3C Recommendation September, 2006.
• 5: D. Chamberlin, D. Florescu, and J. Robie. XQuery Update Facility. Technical report, W3C Working Draft 11 July, 2006.
• 6: Sankhayan Choudhury , Nabendu Chaki , Swapan Bhattacharya, GDM: a new graph based data model using functional abstractionx, Journal of Computer Science and Technology, v.21 n.3, p.430-438, May 2006 [doi>10.1007/s11390-006-0430-0]
• 7: Brian Cooper , Neal Sample , Michael J. Franklin , Gisli R. Hjaltason , Moshe Shadmon, A Fast Index for Semistructured Data, Proceedings of the 27th International Conference on Very Large Data Bases, p.341-350, September 11-14, 2001
• 8: S. DeRose, E. Maler, and D. Orchard. XML Linking Language (XLink)Version 1.0. Technical report, W3C Recommendation 27 June, 2001.
• 9: D. Draper, P. Fankhauser, M. Fernández, A. Malhotra, K. Rose, M. Rys, J. Simeon, and P. Wadler. XQuery 1.0 and XPath 2.0 Formal Semantics.Technical report, W3C Recommendation 23 January, 2007.
• 10: P. Fankhauser, M. Fernandez, A. Malhotra, M. Rys, J. Simeon, and P. Wadler. The XML Query Algebra. Technical report, W3C Working Draft 04 December, 2000.
• 11: M. Fernández, A. Malhotra, J. Marsh, M. Nagy, and N. Walsh. XQuery 1.0 and XPath 2.0 Data Model (XDM). Technical report, W3C Recommendation 23 January, 2007.
• 12: Roy Goldman , Jennifer Widom, DataGuides: Enabling Query Formulation and Optimization in Semistructured Databases, Proceedings of the 23rd International Conference on Very Large Data Bases, p.436-445, August 25-29, 1997
• 13: P. Grosso, E. Maler, J. Marsh, and N. Walsh. XPointer element()Scheme. Technical report, W3C Recommendation 25 March, 2003.
• 14: T. Grust and J. Teubner. Relational Algebra: Mother Tongue -XQuery: Fluent. In TDM pages 9--16, 2004.
• 15: H. He and A. K. Singh. GraphQL: Query Language and Access Methods for Graph Databases. Technical report, Department of Computer Science at University of California, Santa Barbara, 2007.
• 16: I. Kaplan. A Semantic Graph Query Language. Technical report, Lawrence Livermore National Laboratory, 2006.
• 17: Quanzhong Li , Bongki Moon, Indexing and Querying XML Data for Regular Path Expressions, Proceedings of the 27th International Conference on Very Large Data Bases, p.361-370, September 11-14, 2001
• 18: D. A. Lizorkin, The Query Language to XML Documents Connected by XLink Links, Programming and Computing Software, v.31 n.3, p.133-148, May 2005 [doi>10.1007/s11086-005-0026-4]
• 19: Tova Milo , Dan Suciu, Index Structures for Path Expressions, Proceedings of the 7th International Conference on Database Theory, p.277-295, January 10-12, 1999
• 20: E. Prud 'hommeaux and A. Seaborne. SPARQL Query Language for RDF. Technical report, W3C Candidate Recommendation 14 June, 2007.
• 21: A. S. Balouch. XQuery Optimization and Decomposition Strategies in XML Schema Integration PhD thesis, University of Rostock, Germany, 2006.
• 22: A.-C. Schering, I. Bruder, and H. Meyer. Management of Highly Interconnected Information Units in the Digital Wossidlo Archive. In Proceedings of the 19th GI-Workshop on Foundations of Databases, Germany 2007.
• 23: A Graph Query Language and Its Query Processing, Proceedings of the 15th International Conference on Data Engineering, p.572, March 23-26, 1999
• 24: Wenjun Sun , Kevin Lü, Parallel Query Processing Algorithms for Semi-structured Data, Proceedings of the 14th International Conference on Advanced Information Systems Engineering, p.770-773, May 27-31, 2002
• 25: H. S. Thompson, D. Beech, M. Maloney, and N. Mendelsohn. XML Schema Part 1:Structures Second Edition. Technical report,W3C Recommendation 28 October, 2004.

INDEX TERMS

Primary Classification:
  H. Information Systems
  H.2 DATABASE MANAGEMENT
      H.2.3 Languages

Additional Classification:
  E. Data
  E.1 DATA STRUCTURES
      Subjects: Graphs and networks; Trees

  H. Information Systems
  H.3 INFORMATION STORAGE AND RETRIEVAL
      H.3.7 Digital Libraries

General Terms:
Design, Languages

Keywords:
XML, architecture, digital archive, graphs, query language