【正文】 tion，java平臺(tái)標(biāo)準(zhǔn)版)，JavaEE(Java 2 Platform ,Enterprise Edition，java平臺(tái)企業(yè)版)，JavaME(Java 2 Platform Micro Edition，java平臺(tái)微型版)。（4）第4章為關(guān)鍵字SLCA查詢系統(tǒng)的實(shí)現(xiàn)。本論文一共包括五章內(nèi)容，內(nèi)容包括：緒論、相關(guān)技術(shù)介紹、Index Lookup Eager算法原理與實(shí)現(xiàn)、關(guān)鍵字SLCA查詢系統(tǒng)的實(shí)現(xiàn)、軟件測(cè)試，具體如下：（1）第1章為緒論。(2) XSeek區(qū)分代表實(shí)體的節(jié)點(diǎn)和代表屬性的節(jié)點(diǎn)，并返回與關(guān)鍵字匹配的實(shí)體節(jié)點(diǎn)。VLCA包含滿足如下條件的節(jié)點(diǎn)：如果一個(gè)XML節(jié)點(diǎn)包含至少一個(gè)關(guān)鍵字匹配，并且它的子節(jié)點(diǎn)都沒(méi)有包含關(guān)鍵字的匹配，則稱(chēng)該節(jié)點(diǎn)為一個(gè)VLCA節(jié)點(diǎn)。然而該類(lèi)的查詢語(yǔ)言的缺陷是很明顯的：首先，查詢語(yǔ)言的使用者必須學(xué)習(xí)相關(guān)的語(yǔ)法機(jī)制，這一點(diǎn)本身就加強(qiáng)了用戶使用它的難度。因此，大多將研究的重點(diǎn)放在純關(guān)鍵字查詢中。這使得XML類(lèi)型的數(shù)據(jù)成為當(dāng)前流行的數(shù)據(jù)形式，對(duì)XML數(shù)據(jù)的有效管理也隨之成為當(dāng)前數(shù)據(jù)庫(kù)領(lǐng)域研究的熱點(diǎn)。XML上的關(guān)鍵字檢索由于不需要對(duì)XML的模式有所了解,對(duì)用戶來(lái)說(shuō)是簡(jiǎn)單而實(shí)用的?，F(xiàn)已有相當(dāng)多的企業(yè)或組織，將資料以XML表示，以便網(wǎng)絡(luò)上的資料交換與處理。XML（Extend MARKUP Language）由于其具有的子描述性、靈活的數(shù)據(jù)結(jié)構(gòu)以及豐富的數(shù)據(jù)表示能力等特點(diǎn)，現(xiàn)在已經(jīng)被廣泛應(yīng)用到Internet智能信息檢索、電子商務(wù)中的數(shù)據(jù)表示和數(shù)據(jù)交換、數(shù)據(jù)集成、Web Service、數(shù)字圖書(shū)館等領(lǐng)域。由于后者引入的標(biāo)簽信息使得用戶還要了解XML數(shù)據(jù)的實(shí)際組織，增加了用戶使用的復(fù)雜性，而從本質(zhì)上講，這種擴(kuò)散關(guān)鍵字的方式只是增加了過(guò)濾關(guān)鍵字節(jié)點(diǎn)的作用，實(shí)際處理與純關(guān)鍵字方式并無(wú)本質(zhì)區(qū)別。目前，該類(lèi)查詢語(yǔ)言發(fā)展到現(xiàn)在已經(jīng)出現(xiàn)了集中的趨勢(shì)，其代表為W3C推出的Xpath和 Xquery。即，SLCA給出了一個(gè)最小樹(shù)，該樹(shù)包含了所有的關(guān)鍵字，且該樹(shù)的任一子樹(shù)都不完全包含所有關(guān)鍵字。(1) XRANK是最早將XML文檔的分層和超級(jí)鏈接結(jié)構(gòu)、關(guān)鍵字二維接近 的概念考慮進(jìn)來(lái)的XML檢索系統(tǒng)，其設(shè)計(jì)目標(biāo)是為用戶提供類(lèi)似Google的基于超鏈接的HTML搜索引擎，并且支持HTML和XML混合文檔查詢。根據(jù)用戶輸入的關(guān)鍵字有效的計(jì)算關(guān)鍵字的SLCA。詳細(xì)說(shuō)明了程序中關(guān)于ILE算法的幾個(gè)主要函數(shù)的作用和原理。Java程序設(shè)計(jì)語(yǔ)言近年來(lái)得到普及的原因，主要是它的安全性和跨平臺(tái)性兩大特點(diǎn)。企業(yè)版本幫助開(kāi)發(fā)和部署可移植、健壯、可伸縮且安全的服務(wù)器端 Java 應(yīng)用程序。它的優(yōu)良特性使得Java應(yīng)用具有無(wú)比的健壯性和可靠性，這也減少了應(yīng)用系統(tǒng)的維護(hù)費(fèi)用?？梢哉f(shuō)MyEclipse幾乎囊括了目前所有主流開(kāi)源產(chǎn)品的專(zhuān)屬eclipse開(kāi)發(fā)工具。目前MySQL被廣泛地應(yīng)用在Internet上的中小型網(wǎng)站中。而專(zhuān)門(mén)運(yùn)行在x86平臺(tái)的Jrocket在服務(wù)器端運(yùn)行效率也要比Sun JDK好很多。Javah：產(chǎn)生可以調(diào)用Java過(guò)程的C過(guò)程，或建立能被Java程序調(diào)用的C過(guò)程的頭文件。 : 這個(gè)是JSP,Servlet等使用到的類(lèi)。首先，給出XML數(shù)據(jù)及XML文檔樹(shù)的定義。常用的模式包括DTD和 XML Schema。為此，提出最緊致片段的概念，最緊致片段指在XML文檔樹(shù)中，滿足所有查詢關(guān)鍵字組合語(yǔ)義的最小樹(shù)片段，這樣，XML關(guān)鍵字查詢問(wèn)題便轉(zhuǎn)化為查找所有最緊致片段的問(wèn)題。uv(uv)表示在XML樹(shù)前序遍歷中，u的序列在v之前 (之后)，但u并不是v的祖先(后代)。產(chǎn)生該問(wèn)題的原因在于結(jié)果集中的某些LCA節(jié)點(diǎn)是另一些LCA節(jié)點(diǎn)的祖先節(jié)點(diǎn)，這些祖先節(jié)點(diǎn)與查詢關(guān)鍵字之間的相關(guān)度明顯較低。因此，該查詢的輸出為SLCASet={paper(12)，paper(15)}。前綴編碼直接將一個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)的編碼作為該節(jié)點(diǎn)編碼的前綴。全局編碼有效的支持了祖先后代等包含先后關(guān)系的運(yùn)算，而局部編碼可以有效的進(jìn)行左右兄弟關(guān)系的判斷。若不存在，則x為null。之后，使用removeAncestor算法將非最緊致片段節(jié)點(diǎn)去除，即將待求解的Dewey碼集合中的每個(gè)元素使用性質(zhì)3．2。amp。第10行和第11行代碼將上次計(jì)算的最后一個(gè)節(jié)點(diǎn)保留，因?yàn)檫@個(gè)結(jié)果需要被檢驗(yàn)，才能判定是否是SLCA節(jié)點(diǎn)。第3行v=，其左匹配為null，而這都是通過(guò)帶索引的關(guān)鍵字與對(duì)應(yīng)Dewey碼為條目的B+樹(shù)索引實(shí)現(xiàn)的。ILE算法的復(fù)雜度為O(||kdlog|S|)，其中表示含有Dewey碼數(shù)目最少的關(guān)鍵字集合，k為關(guān)鍵字?jǐn)?shù)目，d為Dewey碼長(zhǎng)度，也是descendant的復(fù)雜度，S取法與相反，即含有集合數(shù)目最多的集合。 ILE算法的實(shí)現(xiàn)ILE算法實(shí)現(xiàn)首先需要解決的是數(shù)據(jù)結(jié)構(gòu)的問(wèn)題。接口外，此類(lèi)還提供一些方法來(lái)操作內(nèi)部用來(lái)存儲(chǔ)列表的數(shù)組的大小。針對(duì)上節(jié)提出的ILE算法的不足，在本程序中對(duì)XML結(jié)構(gòu)樹(shù)的編碼使用類(lèi)Dewey編碼，即先序遍歷結(jié)構(gòu)樹(shù)，每個(gè)節(jié)點(diǎn)的編碼即是本節(jié)點(diǎn)從根節(jié)點(diǎn)開(kāi)始的所有祖先構(gòu)成的數(shù)組。具體算法：左匹配：public ArrayListInteger lm(ArrayListIntegerv, ArrayListArrayListIntegerS1) { int i。amp。 } for(i=0。 } else { ArrayListInteger m1=new ArrayListInteger()。 else break。 } else if (v1!=null amp。 } if (c d) { return v1。 for (i=1。 第4章 SLCA查詢系統(tǒng)的實(shí)現(xiàn) 數(shù)據(jù)庫(kù)的實(shí)現(xiàn)，要使得文檔可帶入程序中進(jìn)行計(jì)算必須對(duì)文檔進(jìn)行解析。為了使ER圖表示的更加清晰，先將ER圖分成實(shí)體及其屬性圖和實(shí)體及其聯(lián)系圖。然后進(jìn)行一些設(shè)置。（5） 安裝和配置JDBC驅(qū)動(dòng)。圖43 主頁(yè)面圖43 XML文檔顯示頁(yè)面在MyEclipse中建立新的工程名為XKComp_Demo,，第三章中實(shí)現(xiàn)的程序在該類(lèi)中完成，通過(guò)連接數(shù)據(jù)庫(kù)來(lái)獲得關(guān)鍵字的編碼將n個(gè)關(guān)鍵字對(duì)應(yīng)的編碼以string類(lèi)型的形式放到ArrayList數(shù)組中。 for(int j=0。 } (al_1)。 第5章 軟件測(cè)試在開(kāi)發(fā)軟件系統(tǒng)的過(guò)程中，需要面對(duì)錯(cuò)綜復(fù)雜的問(wèn)題，因此，在軟件生存周期的每個(gè)階段都不可避免地會(huì)產(chǎn)生錯(cuò)誤。這一階段的任務(wù)，是通過(guò)了單元測(cè)試的模塊逐步組裝起來(lái)，通過(guò)測(cè)試與糾錯(cuò)，最終得到一個(gè)滿足需求的目標(biāo)軟件。把經(jīng)過(guò)測(cè)試的子系統(tǒng)裝配成一個(gè)完整的系統(tǒng)進(jìn)行測(cè)試，通過(guò)黑盒測(cè)試與白盒測(cè)試相結(jié)合的方式，對(duì)整個(gè)系統(tǒng)的各個(gè)功能模塊進(jìn)行了測(cè)試，并調(diào)試改正其中的設(shè)計(jì)和編碼錯(cuò)誤，經(jīng)過(guò)這個(gè)環(huán)節(jié)的操作，整個(gè)系統(tǒng)的功能基本實(shí)現(xiàn)成功運(yùn)行。本系統(tǒng)采用單機(jī)的操作界面樣式，操作簡(jiǎn)明直接。參考文獻(xiàn)[1] Yu Xu,Yannis Keyword Search for Smallest LCAs in XML SIGMOD 2005,Baltimore,Maryland,2005[2] Kong LB，Tang SW，Yang DQ，Wang TJ，Gao J．Querying techniques for XML of Software，2007，1 8(6)．[3] Z．Liu and Y．Chen．Identifying meaningful return information for xml keyword search．In SIGMOD，2007．[4] Guo L，Shao F，Botev C，Shanmugasundaram J．XRANK：Ranked keyword search over XML documents．In：Halevy AY，Ives ZG，Dean A，eds．Proc．of the 2003 ACM SIGMOD Int’l Conf．on Management of Data(SIGMOD)．San Diego：ACM Press，2003．1 6—27．[5] and R E．Tarjan．Fast algorithms for finding nearest mon ancestors．In SlAM J．Comput．13(2)，pages 338355，1984．[6] and U．Vishkin．On finding lowest mon ancestors： Simplification and parallelization．SIAM J．Computing，17(6)：12531262，988．[7] ．New algorithms for the LCA problem and the binary tree reconstruction problem．Information Processing．Lett，51(1)：ll16，1994．[8] Kong LB，Tang SW，Yang DQ，Wang TJ，Gao J．Layered solution for SLCA problem in XML information retrieval．Joumal of Software，2007，18(4)． ：//．[9] Henry ，David Beech，Murray Maloney，Noah Mendelsohn．XML Schema Part 1:Structures Second Edition，2004． ：//．w3．org/TR/xmlschema1/nonnormative—schemaDTD[10] Dietz P F．Maintaining order in linked list．ACM Symposium on Theory of Computing 1 982． [11] Online Computer Library Center．Dewey decimal classification． [12] （第二版）.北京：清華大學(xué)出版社，2010年，1212[13] Server 2000數(shù)據(jù)庫(kù)應(yīng)用開(kāi)發(fā)．北京：電子工業(yè)出版社，2001年，160190 [14] 施伯樂(lè)，丁寶康，（第三版）.北京：高等教育出版社，2008年，1179[15] 張娜，陳寧，金焱， Web ：清華大學(xué)出版社，2012年，1164[16] S. Agrawal, S. Chaudhuri, and G. Das. DBXplorer: A system for keywordbased search over relational databases. InICDE,2002.[17] V. Aguilera et al. Querying XML documents in XYleme. In SIGIR Workshop on XML and Information Retrieval, 2000.[18] 陳維興,++ 2004年[19] 嚴(yán)蔚敏,(C語(yǔ)言版).清華大學(xué)出版社 1997年致謝 致謝畢業(yè)設(shè)計(jì)作為我大學(xué)階段的最后一次作業(yè)，完成了它我大學(xué)生活就接近了尾聲。通常在web上的關(guān)鍵字搜索，如Google或者百度，他們返回的結(jié)果是包括用戶提供關(guān)鍵字的整個(gè)網(wǎng)頁(yè)，屬于文檔級(jí)。對(duì)算法在時(shí)間復(fù)雜度和空間復(fù)雜度上進(jìn)行比較，得到最優(yōu)的算法。五、 主要參考文獻(xiàn) [1] Yu Xu,Yannis Keyword Search for Smallest LCAs in XML SIGMOD 2005,Baltimore,Maryland,2005[2] 陳維興,++ 2004年[3] 嚴(yán)蔚敏,(C語(yǔ)言版).清華大學(xué)出版社 1997年[4] ,:A system for keywordbased search over relational 2002[5] et XML documents in Workshop on XML and Information Retrieval 2002.[6] , pattern 2003[7] BerkeleyDB.[8] ,. Keyword searching and browsing in databases using 2002[9] , twig matches in a tree ICDE 2001[10] ,:A semantic search engine for 2003[11] 謝濤,王曉玲,歐陽(yáng)樹(shù)生, .2006 第z3期 [12] H. GarciaMolina, J. Ullman, and J. Widom. DatabaseSystem Implementation. PrenticeHall 2000[13] N. Fuhr and K. Grojohann. XIRQL: A Query Language forInformation Retrieval in XML documents. SIGIR, 2001.[14] V. Hristidis and Y. Papakonstantinou. Discover: Keywordsearch in relational databases. VLDB 2002.[15] V. Hristidis, Y. Papakonstantinou, and A. Balmin. Keywo