Navegar

Colección

Datos Estadísticas

Artículo

Estamos trabajando para incorporar este artículo al repositorio
Consulte el artículo en la página del editor
Consulte la política de Acceso Abierto del editor

Abstract:

In this paper we address the problem of modeling and implementing temporal data in XML. We propose a data model for tracking historical information in an XML document and for recovering the state of the document as of any given time. We study the temporal constraints imposed by the data model, and present algorithms for validating a temporal XML document against these constraints, along with methods for fixing inconsistent documents. In addition, we discuss different ways of mapping the abstract representation into a temporal XML document, and introduce TXPath, a temporal XML query language that extends XPath 2.0. In the second part of the paper, we present our approach for summarizing and indexing temporal XML documents. In particular we show that by indexing continuous paths, i.e., paths that are valid continuously during a certain interval in a temporal XML graph, we can dramatically increase query performance. To achieve this, we introduce a new class of summaries, denoted TSummary, that adds the time dimension to the well-known path summarization schemes. Within this framework, we present two new summaries: LCP and Interval summaries. The indexing scheme, denoted TempIndex, integrates these summaries with additional data structures. We give a query processing strategy based on TempIndex and a type of ancestor-descendant encoding, denoted temporal interval encoding. We present a persistent implementation of TempIndex, and a comparison against a system based on a non-temporal path index, and one based on DOM. Finally, we sketch a language for updates, and show that the cost of updating the index is compatible with real-world requirements. © 2007 Springer-Verlag.

Registro:

Documento: Artículo
Título:Temporal XML: Modeling, indexing, and query processing
Autor:Rizzolo, F.; Vaisman, A.A.
Filiación:Department of Computer Science, University of Toronto, Bahen Center for Information Technology, 40 St. George St., Toronto, ON M5S 2E4, Canada
Universidad de Chile, Universidad de Buenos Aires, Pabellon I, Buenos Aires, Argentina
Palabras clave:Semistructured data; Structural summaries; Temporal databases; XML; XPath
Año:2008
Volumen:17
Número:5
Página de inicio:1179
Página de fin:1212
DOI: http://dx.doi.org/10.1007/s00778-007-0058-x
Título revista:VLDB Journal
Título revista abreviado:VLDB J.
ISSN:10668888
Registro:https://bibliotecadigital.exactas.uba.ar/collection/paper/document/paper_10668888_v17_n5_p1179_Rizzolo

Referencias:

  • Abiteboul, S., Cluet, S., Ferran, G., Rousset, M.-C., The Xyleme project (2002) Comput. Netw., 39, pp. 225-238. , 3
  • Amagasa, T., Yoshikawa, M., Uemura, S., A temporal data model for XML documents (2000) Proceedings of DEXA Conference, pp. 334-344
  • Bozkaya, T., Ozsoyoglu, M., Indexing valid time intervals (1998) Proceedings of DEXA Conference, pp. 541-550
  • Buneman, P., Davidson, S., Fan, W., Hara, C., Tan, W., Keys for XML (2002) Comput. Netw., 39, pp. 473-487. , 5
  • Buneman, P., Khanna, S., Tajima, K., Tan, W., Archiving scientific data (2002) Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 1-12. , Madison, USA
  • Chawathe, S., Abiteboul, S., Widom, J., Managing historical semistructured data (1999) Theory and Practice of Object Systems, 5 (3), pp. 143-162. , Wiley, New York
  • Chawathe, S., Molina, H.G., Ireland, K., Papakonstantinou, Y., Ullman, J., Widom, J., The TSIMMIS project: Integration of heterogeneous information sources (1994) Proeedings of 100th Anniversary Meeting of the Information Processing Society of Japan, pp. 7-18
  • Chien, S., Tsotras, V., Zaniolo, C., Version management of XML documents (2000) Proceedings of the Third International Workshop on the Web and Databases, pp. 75-80. , Dallas, TX
  • Chien, S., Tsotras, V., Zaniolo, C., Efficient management of multiversion documents by object referencing (2001) Proceedings of the 27th International Conference on Very Large Data Bases, pp. 291-300. , Rome, Italy
  • Chomicki, J., Temporal query languages: A survey (1994) Proceedings of the 1st International Conference on Temporal Logic, LNAI 827, pp. 506-534
  • Chung, C.-W., Min, J.-K., Shim, K., APEX: An adaptive path index for XML data (2002) Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 121-132
  • Clifford, J., Dyreson, C.E., Isakowitz, T., Jensen, C.S., Snodgrass, R.T., On the semantics of "now" in databases (1997) ACM Trans. Datab. Syst., 22, pp. 171-214. , 2
  • Consens, M.P., Milo, T., Optimizing queries on files (1994) Proceedings of the 1994 ACM SIGMOD International Conference on Management of Data, pp. 301-312
  • De Capitani, S., An authorization model for temporal XML documents (2002) Proceedings of SAC'02, pp. 1088-1093. , Madrid, Spain
  • Drukh, N., Polyzotis, N., Garofalakis, M.N., Matias, Y., Fractional XSKETCH synopses for XML databases (2004) Proceedings of Second International XML Database Symposium, XSym 2004, pp. 189-203
  • Dyreson, C., Snodgrass, R., Supporting valid-time indeterminacy (1998) ACM Trans. Datab. Syst., 23, pp. 1-57. , 1
  • Dyreson, C.E., Observing transaction-time semantics with TTXPath (2001) Proceedings of WISE 2001, pp. 193-202
  • Dyreson, C.E., Bolen, M.H., Jensen, C.S., Capturing and querying multiple aspects of semistructured data (1999) Proceedings of the 25th VLDB Conference, pp. 290-301
  • Temporal Databases: Research and Practice (1998) LNCS, 1399. , Etzion, O., Jajodia, S., Sripada, S. (eds) Springer, Heidelberg
  • Fan, W., Siméon, J., Integrity constraints for XML (2003) J. Comput. Syst. Sci., 66, pp. 254-291. , 1
  • Florescu, D., Kossmann, D., Storing and querying XML data using a RDBMS (1999) IEEE Data Eng. Bull., 22, pp. 27-34. , 3
  • Gao, C., Snodgrass, R., Syntax, semantics and query evaluation in the τxQuery temporal XML query language (2003) Time Center Technical Report, TR-72
  • Gao, C., Snodgrass, R., Temporal slicing in the evaluation of XML queries (2003) Proceedings of the 29th International Conference on Very Large Data Bases, pp. 632-643. , Berlin, Germany
  • Gergatsoulis, M., Stavrakas, Y., Representing changes in XML documents using dimensions (2003) Proceedings of the First Symposium on XML Databases (XSym 2003), pp. 208-222. , Berlin, Germany
  • Goldman, R., Widom, J., Dataguides: Enabling query formulation and optimization in semistructured databases (1997) Proceedings of the 23rd International Conference on Very Large Data Bases, pp. 436-445
  • Grandi, F., Introducing an annotated bibliography on temporal and evolution aspects in the world wide web (2004) SIGMOD Rec., 33, pp. 4-86. , 2
  • Grandi, F., Mandreoli, F., The valid web: An XML/XSL infrastructure for temporal management of web documents (2000) Proceedings of the International Conference on Advances in Information Systems, pp. 294-303
  • Grandi, F., Mandreoli, F., Effective representation and efficient management of indeterminate dates (2001) TIME'01, pp. 164-169
  • He, H., Yang, J., Multiresolution indexing of XML for frequent queries (2004) Proceedings of the 20th International Conference on Data Engineering, pp. 683-694
  • Kaplan, H., Milo, T., Shabo, R., A comparison of labeling schemes for ancestor queries (2002) Proceedings of the Thirteenth Annual ACM-SIAM Symposium on Disete Algorithms, pp. 954-963
  • Kaushik, R., Bohannon, P., Naughton, J.F., Korth, H.F., Covering indexes for branching path queries (2002) Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 133-144
  • Kaushik, R., Bohannon, P., Naughton, J.F., Shenoy, P., Updates for structure indexes (2002) Proceedings of the 28th International Conference on Very Large Data Bases, pp. 239-250
  • Kaushik, R., Shenoy, P., Bohannon, P., Gudes, E., Exploiting local similarity for indexing paths in graph-structured data (2002) Proceedings of the 18th International Conference on Data Engineering, pp. 129-140
  • Liefke, H., Suciu, D., XMILL: An efficient compressor for XML data (2000) Proceedings of the 2000 ACM SIGMOD International Conference on Management of Data, pp. 153-164
  • Manukyan, M.G., Kalinichenko, L.A., Temporal XML (2001) Proceedings of ADBIS, pp. 581-590. , Vilnius, Lithuania
  • Marian, A., Abiteboul, S., Cobena, G., Mignet, L., Change-centric management of versions in an XML warehouse (2001) Proceedings of the 27th VLDB Conference, pp. 581-590. , Rome, Italy
  • Mendelzon, A.O., Rizzolo, F., Vaisman, A., Indexing temporal XML documents (2004) Proceedings of the 30th International Conference on Very Large Databases, pp. 216-227. , Toronto, Canada
  • Milo, T., Suciu, D., Index structures for path expressions (1999) Proceedings of the 7th International Conference on Database Theory, pp. 277-295
  • Nestorov, S., Ullman, J.D., Wiener, J.L., Chawathe, S.S., Representative objects: Concise representations of semistructured, data (1997) Proceedings of the 13th International Conference on Data Engineering, pp. 79-90
  • Oliboni, B., Quintarelli, E., Tanca, L., Temporal aspects of semistructured data (2001) Proceedings of the Eight International Symposium of Temporal Representation and Reasoning, pp. 119-127
  • Polyzotis, N., Garofalakis, M.N., Statistical synopses for graph-structured XML databases (2002) Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, pp. 358-369
  • Polyzotis, N., Garofalakis, M.N., Structure and value synopses for XML data graphs (2002) Proceedings of the 28th International Conference on Very Large Data Bases, pp. 466-477
  • Polyzotis, N., Garofalakis, M.N., XCLUSTER synopses for structured XML content (2006) Proceedings of the 22nd International Conference on Data Engineering
  • Polyzotis, N., Garofalakis, M.N., Ioannidis, Y.E., Approximate XML query answers (2004) Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, pp. 263-274
  • Qun, C., Lim, A., Ong, K.W., D(k)-index: An adaptive structural summary for graph-structured data (2003) Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, pp. 134-144
  • Rizzolo, F., Mendelzon, A.O., Indexing XML data with ToXin (2001) Proceedings of 4th International Workshop on the Web and Databases, pp. 49-54
  • Salzberg, B., Tsotras, V., Comparison of access methods for time-evolving data (1999) ACM Comput. Surv., 31, pp. 158-221. , 2
  • Santoro, N., Khatib, R., Labelling and implicit routing in networks (1985) Comput. J., 28, pp. 5-8. , 1
  • Schenkel, R., Theobald, A., Weikum, G., HOPI: An efficient connection index for complex XML document collections (2004) Proceedings of the 9th Conference on Extending Database, pp. 237-255
  • (2006) Sleepycat Software: Berkeley DB Java Edition, , http://www.sleepycat.com/products/bdbje.html
  • Snodgrass, R., (1995) The TSQL2 Temporal Query Language, , Kluwer Academic Publishers Dordnecht
  • (1993) Temporal Databases: Theory, Design and Implementation, , Tansel, A., Clifford, J., Gadia, S. (eds.) Benjamin/Cummings, Reading
  • Tatarinov, I., Ives, G., Halevy, A., Weld, D., Updating XML (2001) Proceedings of ACM SIGMOD Conference, pp. 413-424. , Santa Barbara, California
  • Wadler, P., A formal semantics of patterns in XSLT (1999) Markup Technologies, pp. 183-202. , IEEE Computer Society, Philadelphia
  • Wang, F., Zaniolo, C., Temporal queries in XML document archives and web warehouses (2003) Proceedings of the 10th International Symposium on Temporal Representation and Reasoning (TIME'03), pp. 47-55. , Cairns, Australia
  • Wang, F., Zaniolo, C., XBiT: An XML-based bitemporal data model (2004) Proceedings of the 23rd International Conference on Conceptual Modeling, pp. 810-824. , Shanghai, China
  • Wang, F., Zhou, X., Zaniolo, C., Efficient XML-based techniques for archiving, querying and publishing the histories of relational databases (2005) Time Center TeEchnical Report
  • Wang, F., Zhou, X., Zaniolo, C., Temporal XML? SQL strikes back! (2005) Proceedings of the 12th International Symposium on Temporal Representation and Reasoning (TIME'05), pp. 47-55. , Burlington, USA
  • (2002) World Wide Web Consortium.: XQuery 1.0: An XML Query Language, , http://www.w3.org/TR/2002/WD-xquery-20021115
  • (2003) World Wide Web Consortium.: XML Path Language XPath 2.0, , http://www.w3.org/TR/2003/WD-xpath20-20030502
  • Yi, K., He, H., Stanoi, I., Yang, J., Inemental maintenance of XML structural indexes (2004) Proceedings of the 2004 ACM SIGMOD International Conference on Management of Data, pp. 491-502

Citas:

---------- APA ----------
Rizzolo, F. & Vaisman, A.A. (2008) . Temporal XML: Modeling, indexing, and query processing. VLDB Journal, 17(5), 1179-1212.
http://dx.doi.org/10.1007/s00778-007-0058-x
---------- CHICAGO ----------
Rizzolo, F., Vaisman, A.A. "Temporal XML: Modeling, indexing, and query processing" . VLDB Journal 17, no. 5 (2008) : 1179-1212.
http://dx.doi.org/10.1007/s00778-007-0058-x
---------- MLA ----------
Rizzolo, F., Vaisman, A.A. "Temporal XML: Modeling, indexing, and query processing" . VLDB Journal, vol. 17, no. 5, 2008, pp. 1179-1212.
http://dx.doi.org/10.1007/s00778-007-0058-x
---------- VANCOUVER ----------
Rizzolo, F., Vaisman, A.A. Temporal XML: Modeling, indexing, and query processing. VLDB J. 2008;17(5):1179-1212.
http://dx.doi.org/10.1007/s00778-007-0058-x