臺灣博碩士論文加值系統

基於XML的簡單、通用性和實用性，它已經被廣泛地應用在服務計算領域中。在一般情況下，處理XML文件中包含兩個階段：解析XML文件和對XML文件進行查詢。但使用正規表示式來查詢XML文件是一種耗費時間的過程。針對正規表示式的字串匹配和在資料庫查詢XML內容已經有不少的研究在進行不同程度的優化，但基於記憶體表示模型中進行XML正規表示式查詢的相關研究卻很少。在這篇論文中，我們提出一個以完全索引方式設計的記憶體表示模型，稱之為FulDex，以用來提供高效率的XML正規表示式查詢。該模型的關鍵特徵是把XML文件中的元素和屬性的所有字元進行索引到一張索引表中，該表是用在查詢時減少需要被使用正規表示式進行匹配的候選結果數量。我們的實驗結果顯示了FulDex相對於其他7種工具在94%的情況中的平均執行時間更為優秀。而針對大型的XML檔案（1.58GB）中，FulDex的正規表示式查詢的平均執行時間比RapidXML減少93.05%。

XML has been widely used in the field of service computing because of its simplicity, generality and usability. In general, there are two phases in processing an XML document: parsing the XML document and querying over the XML document. However, querying over XML documents with regular expressions is a time intensive process. Although efforts have been made on optimizing regular expression string matchings and XML queries based on database, little emphasis has been put on optimizing XML regular expression queries based on memory representations. In this work, we present a fully-indexing-enabled memory representation, called FulDex, for supporting efficient XML regular expression queries. The key feature of the model is providing an index table for indexing all characters of elements and attributes inside a document so as to decrease the number of candidates that need to be matched with a regular expression query. The experimental results show that the average execution time of FulDex is superior to the one of the other 7 tools with 94% cases; and the average execution time of FulDex for a regular expression query over a large XML document (1.58GB) is 93.05% less than the one of RapidXML.

摘要 iv
Abstract v
Acknowledgements vi
Table of Contents viii
List of Tables ix
List of Figures x
Chapter 1. Introduction 1
Chapter 2. Related Work 3
2.1 Data Structure for Storage Representation 3
2.2 XPath and XQuery. 5
2.3 XML Processing Tools 5
Chapter 3. FulDex: A Fully-Indexing-Enabled Memory Representation Model 8
3.1 Memory Representation Model 8
3.2 Parsing and Building a Memory Representation 9
3.3 Querying with the Memory Representation 12
3.4 APIs for Regular Expression Queries 15
Chapter 4. Experimental Evaluation 17
4.1 Dataset and Queries 17
4.2 Design of Experiment 18
4.3 Experimental Results 19
4.4 Discussion 26
Chapter 5. Conclusion 28
References 29

[1] Document Object Model (DOM) Version 4. http://www.w3.org/TR/dom/.
[2] edX Blog RSS Feed. https://www.edx.org/edx-blog/feed.
[3] Google Maps API Web Services. https://developers.google.com/maps/ web-services/overview.
[4] Google News RSS Feed. http://news.google.com/?output=rss.
[5] jQuery. https://jquery.com/.
[6] pugixml (Light-weight, simple and fast XML parser for C++ with XPath support). http://pugixml.org/.
[7] RapidXml. http://rapidxml.sourceforge.net/.
[8] RFC 4287 – The Atom Syndication Format – IETF Tools. https://tools.ietf. org/html/rfc4287.
[9] RSS 2.0 Specification. https://validator.w3.org/feed/docs/rss2.html.
[10] Scalable Vector Graphics (SVG) 2. http://www.w3.org/TR/SVG2/.
[11] Simple Object Access Protocol (SOAP) 1.2 Specifications. http://www.w3.org/TR/ soap12/.
[12] The Apache Xerces Project. http://xerces.apache.org/.
[13] The XML C parser and toolkit of Gnome. http://www.xmlsoft.org/.
[14] TinyXML-2. http://www.grinninglizard.com/tinyxml2/.
[15] Virtual Token Descriptor for eXtensible Markup Language (VTD-XML). http:// vtd-xml.sourceforge.net/.
[16] XHTML 2.0 Specifications. http://www.w3.org/TR/xhtml2/.
[17] XML API Overview - Cloud Storage - Google Cloud Platform. https://cloud. google.com/storage/docs/xml-api-overview.
[18] XML Path Language (XPath) 3.0. http://www.w3.org/TR/xpath-30/.
[19] XQilla. http://xqilla.sourceforge.net/.
[20] XQuery 3.0: An XML Query Language. http://www.w3.org/TR/xquery-30/.
[21] Xrel: A path-based approach to storage and retrieval of xml documents using relational databases. ACM Trans. Internet Technol., 1(1):110--141, Aug. 2001.
[22] K. Ahmad. A comparative analysis of managing xml data in relational database. In Proceedings of the Third International Conference on Intelligent Information and Database Systems - Volume Part I, ACIIDS'11, pages 100--108, Berlin, Heidelberg, 2011. Springer-Verlag.
[23] M. Becchi and P. Crowley. An improved algorithm to accelerate regular expression evaluation. In Proceedings of the 3rd ACM/IEEE Symposium on Architecture for Net- working and Communications Systems, ANCS '07, pages 145--154, New York, NY, USA, 2007. ACM.
[24] M. Becchi and P. Crowley. Efficient regular expression evaluation: Theory to practice. In Proceedings of the 4th ACM/IEEE Symposium on Architectures for Networking and Communications Systems, ANCS '08, pages 50--59, New York, NY, USA, 2008. ACM.
[25] T. Fahringer, R. Prodan, R. Duan, F. Nerieri, S. Podlipnig, J. Qin, M. Siddiqui, H.-L. Truong, A. Villazon, and M. Wieczorek. Askalon: A grid application development and computing environment. In Proceedings of the 6th IEEE/ACM International Workshop on Grid Computing, GRID '05, pages 122--131, Washington, DC, USA, 2005. IEEE Computer Society.
[26] M. F. Fernandez and D. Suciu. Optimizing regular path expressions using graph schemas. In Proceedings of the Fourteenth International Conference on Data Engi- neering, ICDE '98, pages 14--23, Washington, DC, USA, 1998. IEEE Computer Soci- ety.
[27] D. Ficara, S. Giordano, G. Procissi, F. Vitucci, G. Antichi, and A. Di Pietro. An im- proved dfa for fast regular expression matching. SIGCOMM Comput. Commun. Rev., 38(5):29--40, Sept. 2008.
[28] A. Frisch and L. Cardelli. Greedy regular expression matching. In J. Díaz, J. Karhumäki, A. Lepistö, and D. Sannella, editors, Automata, Languages and Programming, volume 3142 of Lecture Notes in Computer Science, pages 618--629. Springer Berlin Heidel- berg, 2004.
[29] R. Goldman, J. Mchugh, and J. Widom. From semistructured data to xml: Migrating the lore data model and query language. In In ACM SIGMOD WebDB Workshop '99, pages 25--30, 1999.
[30] M. R. Head, M. Govindaraju, R. van Engelen, and W. Zhang. Benchmarking xml pro- cessors for applications in grid web services. In Proceedings of the 2006 ACM/IEEE Conference on Supercomputing, SC '06, New York, NY, USA, 2006. ACM.
[31] H. V. Jagadish, S. Al-Khalifa, A. Chapman, L. V. S. Lakshmanan, A. Nierman, S. Pa- parizos, J. M. Patel, D. Srivastava, N. Wiwatwattana, Y. Wu, and C. Yu. Timber: A native xml database. The VLDB Journal, 11(4):274--291, Dec. 2002.
[32] L. Khan and Y. Rao. A performance evaluation of storing xml data in relational database management systems. In Proceedings of the 3rd International Workshop on Web Infor- mation and Data Management, WIDM '01, pages 31--38, New York, NY, USA, 2001. ACM.
[33] T. C. B. Lam, J. J. Ding, and J.-C. Liu. Xml document parsing: Operational and per- formance characteristics. Computer, 41(9):30--37, Sept. 2008.
[34] Q. Li and B. Moon. Indexing and querying xml data for regular path expressions. In Proceedings of the 27th International Conference on Very Large Data Bases, VLDB '01, pages 361--370, San Francisco, CA, USA, 2001. Morgan Kaufmann Publishers Inc.
[35] W. Meier. exist: An open source native xml database. In Revised Papers from the NODe 2002 Web and Database-Related Workshops on Web, Web-Services, and Database Sys- tems, pages 169--183, London, UK, UK, 2003. Springer-Verlag.
[36] M. Nicola and J. John. Xml parsing: A threat to database performance. In Proceedings of the Twelfth International Conference on Information and Knowledge Management, CIKM '03, pages 175--178, New York, NY, USA, 2003. ACM.
[37] M. L. Noga, S. Schott, and W. Löwe. Lazy xml processing. In Proceedings of the 2002 ACM Symposium on Document Engineering, DocEng '02, pages 88--94, New York, NY, USA, 2002. ACM.
[38] C. Pautasso, O. Zimmermann, and F. Leymann. Restful web services vs. big' web services: Making the right architectural decision. In Proceedings of the 17th Interna- tional Conference on World Wide Web, WWW '08, pages 805--814, New York, NY, USA, 2008. ACM.
[39] G. Psaila. Virtual dom: An efficient virtual memory representation for large xml doc- uments. In Proceedings of the 2008 19th International Conference on Database and Expert Systems Application, DEXA '08, pages 233--237, Washington, DC, USA, 2008. IEEE Computer Society.
[40] A. Salminen and F. Tompa. Processors and applications. In Communicating with XML, chapter 2.2, pages 24 -- 26. Springer Publishing Company, Incorporated, 1 edition, 2011.
[41] A. Schmidt, M. L. Kersten, M. Windhouwer, and F. Waas. Efficient relational storage and retrieval of xml documents. In Selected Papers from the Third International Work- shop WebDB 2000 on The World Wide Web and Databases, pages 137--150, London, UK, UK, 2001. Springer-Verlag.
[42] J. Shanmugasundaram, E. Shekita, J. Kiernan, R. Krishnamurthy, E. Viglas, J. Naughton, and I. Tatarinov. A general technique for querying xml documents us- ing a relational database system. SIGMOD Rec., 30(3):20--26, Sept. 2001.
[43] I. Tatarinov, S. D. Viglas, K. Beyer, J. Shanmugasundaram, E. Shekita, and C. Zhang. Storing and querying ordered xml using a relational database system. In Proceedings of the 2002 ACM SIGMOD International Conference on Management of Data, SIGMOD '02, pages 204--215, New York, NY, USA, 2002. ACM.
[44] F. Wang, J. Li, and H. Homayounfar. A space efficient xml dom parser. Data Knowl. Eng., 60(1):185--207, Jan. 2007.
[45] H. Wang, S. Park, W. Fan, and P. S. Yu. Vist: A dynamic index method for querying xml data by tree structures. In Proceedings of the 2003 ACM SIGMOD International Conference on Management of Data, SIGMOD '03, pages 110--121, New York, NY, USA, 2003. ACM.
[46] N. Yamagaki, R. Sidhu, and S. Kamiya. High-speed regular expression matching engine using multi-character nfa. In Field Programmable Logic and Applications, 2008. FPL 2008. International Conference on, pages 131--136, Sept 2008.
[47] Y. Yang and V. Prasanna. Space-time tradeoff in regular expression matching with semi- deterministic finite automata. In INFOCOM, 2011 Proceedings IEEE, pages 1853-- 1861, April 2011.