【正文】 l,)=。而且，雖然B+樹索引結(jié)構(gòu)在現(xiàn)有的數(shù)據(jù)庫管理系統(tǒng)中普遍使用，但是都不適用于Dewey編碼數(shù)據(jù)。在內(nèi)的所有元素。在添加大量元素前，應(yīng)用程序也可以使用ensureCapacity操作來增加ArrayList實例的容量，這可以減少遞增式再分配的數(shù)量。10. 重復(fù)39，直到為空。 pCur = (i)。 } } return (() 1)。 } } return null。i++) { int a=(i)。具體算法如下：public ArrayListInteger descendant(ArrayListInteger v1,ArrayListInteger v2) { if (v1==null amp。 v2!=null) { int c=((0))。 int b=(0)。 } } if(a == i1) { return true。一種完整的方式是，對局部結(jié)構(gòu)中任意兩個實體類型，依據(jù)需求分析的結(jié)果，考察局部結(jié)構(gòu)中任意兩個實體類型之間是否存在聯(lián)系。Keyword_name表用于記錄關(guān)鍵字的信息，當(dāng)用戶輸入關(guān)鍵字時可以通過關(guān)鍵字的名稱到數(shù)據(jù)中提取相應(yīng)的節(jié)點編碼。（2） 配置MySQL數(shù)據(jù)庫。 頁面設(shè)計和實現(xiàn)方法在主頁面上有數(shù)據(jù)庫的選擇，用戶根據(jù)自己的需要選擇數(shù)據(jù)庫，在輸入框中輸入關(guān)鍵字信息單擊Search按鈕便會得到查詢結(jié)果只有在選擇的數(shù)據(jù)庫中包含輸入的關(guān)鍵字時才能得到正確的結(jié)果。//二維 String s=(i)。k。頁面的跳轉(zhuǎn)和出錯處理等操作在servlet中實現(xiàn)。單元測試的用例從單元詳細(xì)設(shè)計中導(dǎo)出。 單元測試（1）程序測試完成對算法的編寫后對程序計算時間進行輸出，從而在時間復(fù)雜度和空間復(fù)雜度上對算法進行改進。從上面的測試中可以看出，此系統(tǒng)可以完成對XML文檔中關(guān)鍵字最低最小公共祖先的查詢。XML關(guān)鍵字查詢的基本問題是求解滿足關(guān)鍵字組合語義的最緊致片段，目前，最好的最緊致片段定義為SLCA。同時，當(dāng)我在畢業(yè)設(shè)計過程中遇到問題和困難時，我的同學(xué)和師兄也給予了很大的幫助，給我提出許多關(guān)鍵性的意見和建議，使我對整個畢業(yè)設(shè)計的思路有了總體的把握，并耐心的幫我解決了許多實際問題，使我獲益良多，是你們教授了我豐富的知識，教會了我學(xué)習(xí)知識的能力，我十分感謝我的同學(xué)們！我十分感謝四年中母校對我的教育和培養(yǎng)，感謝指導(dǎo)老師陳老師，我會繼續(xù)努力，奮發(fā)圖強。 。3. 增加對算法的增刪改查來對不同算法在時間復(fù)雜度和空間復(fù)雜度上進行比較，通過對數(shù)據(jù)集的增刪改查，使算法能夠在不同的數(shù)據(jù)集上執(zhí)行查詢進而比較算法的優(yōu)劣。為每個節(jié)點建立一個一維數(shù)組，以從根節(jié)點開始依次存入該節(jié)點的所有祖先結(jié)點，最后一位是該節(jié)點本身第一位是所輸入節(jié)點個數(shù)。二、 研究的基本內(nèi)容，擬解決的主要問題 XML上的關(guān)鍵字搜索是依據(jù)最低最小公共祖先（SLCA）的原則，返回滿足以下兩點的字的節(jié)點集：(1)所有關(guān)鍵字包含在節(jié)點集中節(jié)點或節(jié)點的子孫中(2)節(jié)點集的子孫節(jié)點中沒有包含所有關(guān)鍵字的節(jié)點。在完成畢業(yè)設(shè)計的工程中，由于自己對知識運用的不夠熟練，以及研究生復(fù)試等諸多原因沒有足夠的時間去完成別業(yè)設(shè)計，在這種情況下，我的指導(dǎo)老師—陳子陽老師給了我很多的幫助和理解，我十分感謝陳老師，是您嚴(yán)謹(jǐn)?shù)闹螌W(xué)，適時的督促，不斷地指導(dǎo)，使我順利完成了我的畢業(yè)設(shè)計。由于XML的廣泛應(yīng)用，從XML數(shù)據(jù)中提取用戶感興趣的信息有著越來越 重要的作用。通過單元測試，查找出了系統(tǒng)各模塊內(nèi)部的錯誤；通過子系統(tǒng)測試，發(fā)現(xiàn)了模塊間相互協(xié)調(diào)和連接上的錯誤；通過系統(tǒng)的集成測試，發(fā)現(xiàn)了軟件設(shè)計過程中存在的錯誤。一般來說，系統(tǒng)測試是功能性測試，不是結(jié)構(gòu)性測試。按照軟件工程的觀點，軟件測試（主要是指多模塊程序的測試）共包括3個層次。在上述程序處理后得到每個關(guān)鍵字的節(jié)點編碼以二維數(shù)組的形式存儲到一個三維數(shù)組中。 String[]node_1=node[j].split(\\.)。i()。（3） 啟動MyEclipse。接下來驗證jdk安裝是否成功，先打開“開始”→“運行”，輸入“cmd”，進入dos系統(tǒng)界面，然后輸入“javaversion”，如果正確輸出java的安裝版本信息，則表示java環(huán)境已經(jīng)順利安裝成功。計算得出結(jié)果為節(jié)點的編碼，于是需要通過編碼的ID號來查詢節(jié)點所對應(yīng)的關(guān)鍵字。在本系統(tǒng)中涉及到的對象是關(guān)鍵字，根據(jù)用戶的需求，使用實體—聯(lián)系圖來建立數(shù)據(jù)模型。 int d=(i)。具體算法如下：public boolean parent(ArrayListInteger paru,ArrayListInteger descv) { if (()==0||()==0) { return false。 } else if(v1!=null amp。 } }在本算法中descendant（）函數(shù)中兩個參數(shù)若都不為空則一定存在父親與孩子的關(guān)系，所以只需返回兩節(jié)點中最后一位小的節(jié)點便是孩子節(jié)點。 for ( i=1。 a=(i)。amp。i ()。圖35xml結(jié)構(gòu)樹編碼ILE算法SLCA的求解過程：1. 根據(jù)輸入的n個關(guān)鍵字在數(shù)據(jù)庫中查找關(guān)鍵字對應(yīng)的編碼；2. 將每個關(guān)鍵字的對應(yīng)的所有節(jié)點編碼作為二維數(shù)組存到一個ArrayList類型的三維數(shù)組中；3. 將三維數(shù)組的第一個二維數(shù)組即第一個關(guān)鍵字對應(yīng)的編碼看做4. 設(shè)定一個合理大?。╬）的緩沖區(qū)間B,將中的p個節(jié)點放入B中令i=2。隨著向ArrayList中不斷添加元素，其容量也自動增長。實現(xiàn)了所有可選列表操作，并允許包括SE利用B+樹葉層次按序排序的事實，使用了游標(biāo)來完成左匹配和右匹配的操作，在此不做詳細(xì)介紹。第2次迭代x=descendant(lca(，lm(，))，lca(，rm(，))) = descendant(1ca(，null)，lca(，))=descendant(nuil,)=。經(jīng)過第4和第5行代碼計算后， B=getslca(get_slca([，]，)，)=getslca([，]，)={[]}。 v is not ancestor of getFirstNode(B)) 9． Output v 1 0． v=removeLastNode(B) 11． Output B12. B={}13． ) 14． Output v15．)算法3．2 getslca(，)算法0．get_slca(，){ 1． Result={} 2． u=0 //u=root initially3． for each node v in { 4． x=descendant(1ca(v , lm(v，))，lca(V，rm(v，))) //pre() denotes the order of lefttoright and depthfirst 5． If(pre(u)=pre(x)){ 6． If(u is not x and u is not ancestor of x) 7． Result=Result {u} 8． u=x9． } 10． }11. Return Result {u} 12．}例如，給定查詢的關(guān)鍵字集合為{“John”，“Ben”，“Class”)，而它們對應(yīng)的Dewey碼集合為={，)，={，．，)，= {，)。B+樹結(jié)構(gòu)應(yīng)實現(xiàn)前文中涉及的兩個基本操作，即左匹配和右匹配操作，從而快速返回某個Dewey碼在另外一個關(guān)鍵字集合中的左匹配編碼和右匹配編碼。計算descendent(u，v)時，如果參數(shù)u，v其中之一為空，則返回另一個非空的Dewey碼：如果v包含u，則返回v，反之返回u。：Dewey編碼，給定對應(yīng)XML文檔的標(biāo)簽有向樹G=(V,E,r,A)，G中任意節(jié)點的Dewey編碼由下列規(guī)則確定： (1)根節(jié)點r的Dewey編碼為0； (2)在對G進行寬度優(yōu)先遍歷的過程中，如果節(jié)點v是節(jié)點u的第i個子節(jié)點，那么，節(jié)點v的Dewey碼為D(u)．(i1)，其中的D(u)表示節(jié)點u的Dewey編碼。 對于前綴編碼，要判斷一個節(jié)點v是否是另外一個節(jié)點u的后裔，只需要判斷字符串c（u）是否是字符串c（v）的前綴。求解SLCA問題的通常的解法可概括如下：首先獲取包含對應(yīng)關(guān)鍵字的葉節(jié)點的集合，標(biāo)記為（1≤i≤k，）即S為包含關(guān)鍵字形的所有葉節(jié)點的集合。即，SLCA給出一個最小樹，該樹包含了所有的關(guān)鍵字，且該樹的任一子樹都不完全包含所有關(guān)鍵字。：LCASet，給定查詢關(guān)鍵字集合K={,．．． }及待查詢XML文檔D，在D上關(guān)于K的LCASet定義為 LCASet=LCA(，…)={ |=LCA（,…），∈ (1≤i≤m)}。在將LCA的概念引入XML關(guān)鍵字查詢中時，LCA指所有包含查詢關(guān)鍵字的節(jié)點的最近公共祖先。XML數(shù)據(jù)的基本形式為XML文檔。符合XML規(guī)范的數(shù)據(jù)稱作XML數(shù)據(jù)，XML規(guī)范規(guī)定了XML數(shù)據(jù)必須滿足的條件。選擇MySQL做后臺數(shù)據(jù)庫管理系統(tǒng)，是因為它能夠在windows XP系統(tǒng)下穩(wěn)定運行、安全可靠，且與MyEclipse兼容性好。常用的package包括：：這個是系統(tǒng)的基礎(chǔ)類，比如String等都是這里面的，這個package是唯一一個可以不用import就可以使用的Package。jar – 打包工具，將相關(guān)的類文件打包成一個文件。MySQL的SQL語言是用于訪問數(shù)據(jù)庫的最常用標(biāo)準(zhǔn)化語言。按照美國國家標(biāo)準(zhǔn)協(xié)會的規(guī)定，SQL被作為關(guān)系型數(shù)據(jù)庫管理系統(tǒng)的標(biāo)準(zhǔn)語言。特別是Java企業(yè)應(yīng)用編程接口（Java Enterprise APIs）為企業(yè)計算及電子商務(wù)應(yīng)用系統(tǒng)提供了有關(guān)技術(shù)和豐富的類庫。這個版本以前稱為 J2ME。Java SE 以前稱為 J2SE。在本章中實現(xiàn)了對整個系統(tǒng)的設(shè)計與實現(xiàn)，由于本文的重心在于實現(xiàn)ILE算法，而系統(tǒng)則起到了輔助的作用，來幫助算法得到完善。（2）第2章為相關(guān)技術(shù)介紹。 XML關(guān)鍵字查詢的基本問題是獲得所有滿足關(guān)鍵字組合語義的最緊致片段，根據(jù)目前的研究，對最緊致片段的定義最好的是SLCA，本文便是圍繞SLCA展開的。SLCA、VLCA、MLCA等的引入，相對于簡單的LCA求解，提高了XML關(guān)鍵字查詢的性能和準(zhǔn)確率。針對絕大多數(shù)用戶并不了解XML文檔結(jié)構(gòu)和查詢語言的現(xiàn)狀，XML關(guān)鍵字查詢提出可以根據(jù)用戶提供的查詢關(guān)鍵字得到用戶期望的信息，不需要用戶了解XML文檔結(jié)構(gòu)及查詢語言，適合絕大多數(shù)用戶使用。分析國內(nèi)外在XML最緊致片段上的研究得知，目前，定義最緊致片段的概念中最好的是SLCA(Smallest Lowest Common Ancestor),因此，本文將重點對SLCA的概念及求解SLCA的算法進行研究，以提高XML關(guān)鍵字查詢的性能和準(zhǔn)確率，這對用戶有著重要的意義。為了從自描述的、半結(jié)構(gòu)化的XML數(shù)據(jù)中抽取用戶感興趣的信息，研究人員開發(fā)了許多查詢描述形式，文獻根據(jù)查詢請求描述特點的不同，可概括為兩大類查詢模式：XML結(jié)構(gòu)化查詢和XML關(guān)鍵字查詢。XML上的關(guān)鍵字檢索不需要用戶對所查詢的XML的DTD或模式、復(fù)雜的XML查詢語言等相關(guān)知識有所了解，因此更容易被用戶接受。近年來，萬維網(wǎng)已經(jīng)成為資訊分享的主要平臺，但是以HTML表示的網(wǎng)頁資料，并不適合自動化處理。所以， 更加詳細(xì)的檢索出用戶所需要的信息是網(wǎng)絡(luò)的迫切需要也是用戶的迫切需要。然而Internet的大多數(shù)使用者，是那些既不懂得查詢語言，又不了解XML文檔結(jié)構(gòu)的普通用戶，這時基于關(guān)鍵字的XML數(shù)據(jù)查詢是比較方便的，他只需要用戶提供簡單的關(guān)鍵字信息，而無需要用戶懂得任何查詢語言或文檔結(jié)構(gòu)。XML結(jié)構(gòu)查詢首先定義精確的查詢描述語言，用戶借助它來描述自己感興趣的數(shù)據(jù)，XML結(jié)構(gòu)查詢引擎返回按照用戶需求的形式化描述而檢索到的XML片段。在LCA的基礎(chǔ)上，又相繼提出了Smallest LCA(SLCA)、Valuable LCA(VLCA)、Meaningful LCA(MLCA)等概念來提高XML關(guān)鍵字查詢的性能和準(zhǔn)確率。由于XML片段具有結(jié)構(gòu)信息，使得針對它的相似性計算可以考慮傳統(tǒng)的相似性計算方法，即可以通過用戶對于結(jié)果的反饋來進一步計算符合用戶意圖的最終結(jié)果。本文設(shè)計開發(fā)一個關(guān)鍵字查詢系統(tǒng)，主要完成查詢關(guān)鍵字最低最小公共祖先的功能。為ILE算法的理論基礎(chǔ)和編程實現(xiàn)。最后為結(jié)論，該部分是對系統(tǒng)的整個開發(fā)設(shè)計過程進行了總結(jié)，包括在系統(tǒng)開發(fā)中應(yīng)用的一些技術(shù)以及系統(tǒng)設(shè)計尚存在的不足和對未來的展望。 Java EE（Java Platform，Enterprise Edition）?；?Java ME 規(guī)范的應(yīng)用程序只需編寫一次，就可以用于許多設(shè)備，而且可以利用每個設(shè)備的本機功能。MyEclipse 是一個十分優(yōu)秀的用于開發(fā)Java, J2EE的 Eclipse 插件集合，MyEclipse的功能非常強大，支持也十分廣泛，尤其是對各種開源產(chǎn)品的支持十分不錯。雖然很多數(shù)據(jù)庫都對SQL語句進行了再開發(fā)和擴展，但是包括Select, Insert, Update, Delete, Create,以及Drop在內(nèi)的標(biāo)準(zhǔn)的SQL命令仍然可以被用來完成幾乎所有的數(shù)據(jù)庫操作。JDK 是整個Java的核心，包括了Java運行環(huán)境，Java工具和Java基礎(chǔ)的類庫。java – 運行編譯后的java程序（.class后綴的）。 : 這個是系統(tǒng)輔助類，特別是集合類Collection,List,Map等。