【正文】 對(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] 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ù)庫應(yīng)用開發(fā)．北京：電子工業(yè)出版社，2001年，160190 [14] 施伯樂，丁寶康，（第三版）.北京：高等教育出版社，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語言版).清華大學(xué)出版社 1997年致謝 致謝畢業(yè)設(shè)計(jì)作為我大學(xué)階段的最后一次作業(yè)，完成了它我大學(xué)生活就接近了尾聲。把經(jīng)過測(cè)試的子系統(tǒng)裝配成一個(gè)完整的系統(tǒng)進(jìn)行測(cè)試，通過黑盒測(cè)試與白盒測(cè)試相結(jié)合的方式，對(duì)整個(gè)系統(tǒng)的各個(gè)功能模塊進(jìn)行了測(cè)試，并調(diào)試改正其中的設(shè)計(jì)和編碼錯(cuò)誤，經(jīng)過這個(gè)環(huán)節(jié)的操作，整個(gè)系統(tǒng)的功能基本實(shí)現(xiàn)成功運(yùn)行。 第5章 軟件測(cè)試在開發(fā)軟件系統(tǒng)的過程中，需要面對(duì)錯(cuò)綜復(fù)雜的問題，因此，在軟件生存周期的每個(gè)階段都不可避免地會(huì)產(chǎn)生錯(cuò)誤。 for(int j=0。（5） 安裝和配置JDBC驅(qū)動(dòng)。為了使ER圖表示的更加清晰，先將ER圖分成實(shí)體及其屬性圖和實(shí)體及其聯(lián)系圖。 for (i=1。 } else if (v1!=null amp。 } else { ArrayListInteger m1=new ArrayListInteger()。amp。針對(duì)上節(jié)提出的ILE算法的不足，在本程序中對(duì)XML結(jié)構(gòu)樹的編碼使用類Dewey編碼，即先序遍歷結(jié)構(gòu)樹，每個(gè)節(jié)點(diǎn)的編碼即是本節(jié)點(diǎn)從根節(jié)點(diǎn)開始的所有祖先構(gòu)成的數(shù)組。 ILE算法的實(shí)現(xiàn)ILE算法實(shí)現(xiàn)首先需要解決的是數(shù)據(jù)結(jié)構(gòu)的問題。第3行v=，其左匹配為null，而這都是通過帶索引的關(guān)鍵字與對(duì)應(yīng)Dewey碼為條目的B+樹索引實(shí)現(xiàn)的。amp。若不存在，則x為null。前綴編碼直接將一個(gè)節(jié)點(diǎn)的雙親節(jié)點(diǎn)的編碼作為該節(jié)點(diǎn)編碼的前綴。產(chǎn)生該問題的原因在于結(jié)果集中的某些LCA節(jié)點(diǎn)是另一些LCA節(jié)點(diǎn)的祖先節(jié)點(diǎn)，這些祖先節(jié)點(diǎn)與查詢關(guān)鍵字之間的相關(guān)度明顯較低。為此，提出最緊致片段的概念，最緊致片段指在XML文檔樹中，滿足所有查詢關(guān)鍵字組合語義的最小樹片段，這樣，XML關(guān)鍵字查詢問題便轉(zhuǎn)化為查找所有最緊致片段的問題。首先，給出XML數(shù)據(jù)及XML文檔樹的定義。Javah：產(chǎn)生可以調(diào)用Java過程的C過程，或建立能被Java程序調(diào)用的C過程的頭文件。目前MySQL被廣泛地應(yīng)用在Internet上的中小型網(wǎng)站中。它的優(yōu)良特性使得Java應(yīng)用具有無比的健壯性和可靠性，這也減少了應(yīng)用系統(tǒng)的維護(hù)費(fèi)用。Java程序設(shè)計(jì)語言近年來得到普及的原因，主要是它的安全性和跨平臺(tái)性兩大特點(diǎn)。根據(jù)用戶輸入的關(guān)鍵字有效的計(jì)算關(guān)鍵字的SLCA。即，SLCA給出了一個(gè)最小樹，該樹包含了所有的關(guān)鍵字，且該樹的任一子樹都不完全包含所有關(guān)鍵字。由于后者引入的標(biāo)簽信息使得用戶還要了解XML數(shù)據(jù)的實(shí)際組織，增加了用戶使用的復(fù)雜性，而從本質(zhì)上講，這種擴(kuò)散關(guān)鍵字的方式只是增加了過濾關(guān)鍵字節(jié)點(diǎn)的作用，實(shí)際處理與純關(guān)鍵字方式并無本質(zhì)區(qū)別。現(xiàn)已有相當(dāng)多的企業(yè)或組織，將資料以XML表示，以便網(wǎng)絡(luò)上的資料交換與處理。這使得XML類型的數(shù)據(jù)成為當(dāng)前流行的數(shù)據(jù)形式，對(duì)XML數(shù)據(jù)的有效管理也隨之成為當(dāng)前數(shù)據(jù)庫領(lǐng)域研究的熱點(diǎn)。然而該類的查詢語言的缺陷是很明顯的：首先，查詢語言的使用者必須學(xué)習(xí)相關(guān)的語法機(jī)制，這一點(diǎn)本身就加強(qiáng)了用戶使用它的難度。(2) XSeek區(qū)分代表實(shí)體的節(jié)點(diǎn)和代表屬性的節(jié)點(diǎn)，并返回與關(guān)鍵字匹配的實(shí)體節(jié)點(diǎn)。（4）第4章為關(guān)鍵字SLCA查詢系統(tǒng)的實(shí)現(xiàn)。Java EE 是在 Java SE 的基礎(chǔ)上構(gòu)建的，它提供 Web 服務(wù)、組件模型、管理和通信 API，可以用來實(shí)現(xiàn)企業(yè)級(jí)的面向服務(wù)體系結(jié)構(gòu)（serviceoriented architecture，SOA）和 Web 應(yīng)用程序。 MySQL介紹SQL(Structured Query Language)，結(jié)構(gòu)化查詢語言。,提供了泛型等非常實(shí)用的功能，其版本也不斷更新，運(yùn)行效率得到了非常大的提高。本章介紹了本系統(tǒng)的開發(fā)環(huán)境。文檔類型定義DTD(Document Type Definition)是一種保證 XML文檔格式正確的有效方法，可以通過比較XML文檔和DTD文件來看文檔是否符合規(guī)范，元素和標(biāo)簽使用是否正確。下面，給出LCA的準(zhǔn)確定義：給定查詢關(guān)鍵字集合K={,．．． }及待查詢關(guān)鍵字文檔D，表示D中直接包含關(guān)鍵字島的節(jié)點(diǎn)集合。SLCA的概念以LCA為基礎(chǔ)，排除了LCA中與查詢關(guān)鍵字相關(guān)度較低的節(jié)點(diǎn)，提高了XML關(guān)鍵字查詢的準(zhǔn)確度，被認(rèn)為是目前最好的最緊致片段的定義。前綴編碼作為全局編碼和局部編碼結(jié)合的方案的混合編碼，有效的繼承了前兩種編碼方案的優(yōu)點(diǎn)，這也是前綴編碼在XML文檔的關(guān)鍵字查詢中能被廣泛使用的原因之一。性質(zhì)3．4表示了實(shí)際計(jì)算SLCA過程中的迭代方案。在第一次迭代結(jié)束后，第11行輸出null。至于對(duì)k個(gè)關(guān)鍵字集合在計(jì)算時(shí)需要使用元素最少的集合作為的取值的原因，從算法復(fù)雜度中可以得出答案，即在k和d，以及查找B+樹結(jié)構(gòu)的復(fù)雜度log|S|作為固定值的情況下，|| 的取值決定了總體的時(shí)間復(fù)雜度。每個(gè)ArrayList實(shí)例都有一個(gè)容量，該容量是指用來存儲(chǔ)列表元素的數(shù)組的大小。 if (()==0) { return null。i()。 } (0, i1)。 } } return null。解析程序由C++語言實(shí)現(xiàn)，這里不再列出具體算法通過解析程序?qū)ML文檔解析后可得到對(duì)應(yīng)的倒排表形式文件。首先右鍵點(diǎn)擊“我的電腦”，打開“屬性”，然后選擇“高級(jí)”里面的“環(huán)境變量”，在新打開界面中的系統(tǒng)變量中需要設(shè)置三個(gè)屬性“JAVA_HOME”、“path”、“classpath”，其中在沒安裝過jdk的環(huán)境下，path的屬性是本來就存在的，而JAVA_HOME 和classpath是不存在的。由于數(shù)據(jù)庫中沒有數(shù)組的存儲(chǔ)形式，因此在數(shù)據(jù)庫設(shè)計(jì)時(shí)采用longtext類型存儲(chǔ)編碼，為了在算法中得到三維數(shù)組的關(guān)鍵字節(jié)點(diǎn)編碼用以下的程序?qū)崿F(xiàn)。 } (al)。（3）驗(yàn)證測(cè)試。該系統(tǒng)基本完成了任務(wù)書中的主要設(shè)計(jì)內(nèi)容的各項(xiàng)任務(wù)，整個(gè)系統(tǒng)也在經(jīng)過測(cè)試和不斷地改正之后能夠順利運(yùn)行。但如果對(duì)大XML文檔上的關(guān)鍵字檢索，由于XML文檔通常被建模成樹形，有著層次性的嵌套關(guān)系，用戶通常希望得到最小結(jié)果片段，此時(shí)查詢力度不再是文檔級(jí)而是元素級(jí)。四、 研究工作進(jìn)度 1－2周：開題報(bào)告、查閱資料，詳細(xì)閱讀論文3－4周：完成由算法到代碼的實(shí)現(xiàn)5－6周：對(duì)程序進(jìn)行調(diào)試7－8周：進(jìn)行算法和數(shù)據(jù)集進(jìn)行增產(chǎn)改查9－12周：閱讀第二個(gè)論文并進(jìn)行代碼的編寫13－15周：調(diào)試程序并對(duì)整個(gè)系統(tǒng)進(jìn)行調(diào)試19－17周：撰寫畢業(yè)論文，準(zhǔn)備驗(yàn)收。XML上的關(guān)鍵字檢索不需要用戶對(duì)復(fù)雜的XML查詢語言等相關(guān)知識(shí)有所了解，因此更容易被用戶接受。 13 結(jié)論本設(shè)計(jì)在Eclipse開發(fā)環(huán)境下，運(yùn)用java編程和SQL Server2000數(shù)據(jù)庫，使用C/S模式，采用圖形化的界面。（2）集成測(cè)試和確認(rèn)測(cè)試。 (t)。具體的界面設(shè)計(jì)如圖43所示，原始的XML文檔如圖44所示。表42 ID索引表名稱類型空默認(rèn)值屬性主索引node_idnode_idint(11)nouniquelatin1lablechar(50)yeslatin1 配置開發(fā)環(huán)境首先下載最新的jdk版本，下載好之后，選擇安裝路徑，安裝到計(jì)算機(jī)上。 } } }在本章中著重介紹了XML數(shù)據(jù)及其樹結(jié)構(gòu)，SLCA的定義及涉及到的一些概念，Index Lookup Eager算法的原理，以及算法的具體實(shí)現(xiàn)。 if (c = d) { return v2。 if(a==b) (a)。 if (()==0) { return null。List最后一次迭代，因?yàn)闆]有待計(jì)算節(jié)點(diǎn)，所以至第10行，返回集合{}。初始時(shí)，v=null，第6到第9行代碼沒有執(zhí)行。性質(zhì)3．3將一個(gè)集合中的每個(gè)Dewey碼v實(shí)施性質(zhì)3．2，從而計(jì)算出多個(gè)SLCA。前綴編碼是一種全局編碼和局部編碼結(jié)合的編碼方式，即混合編碼。定義3．4：SLCASet，給定查詢關(guān)鍵字集合K={,．．．}及待查詢XML文檔D，在D上關(guān)于K的SLCASet定義為：SLCASet=SLCA(，…)={|=LCA（，…），u |vu，u∈LCA（，…）}例如在圖2．3中，盡管在查詢關(guān)鍵字集合{“John”，“Ben”}下conf(2) ∈LCASet，但conf(2)并不在SLCASet中，因?yàn)閜aper(15) ∈LCASet并且conf(2) paper(15)。對(duì)于任意節(jié)點(diǎn)u、v，uv(uv)表示u是v的祖先(后代)，uv表示uv或者u=v。XML數(shù)據(jù)內(nèi)容的限制通常由XML模式來描述。 : 這個(gè)是數(shù)據(jù)庫操作的類，包括Connection, Statement，ResultSet等。JDK是學(xué)好Java的第一步。MyEclipse目前支持Java Servlet ,AJAX, JSP, JSF, Struts,Spring, Hibernate,EJB3,JDBC數(shù)據(jù)庫鏈接工具等多項(xiàng)功能。這個(gè)版本以前稱為 J2EE。主要是對(duì)ILE算法的理論知識(shí)和編程的具體實(shí)現(xiàn)了具體的介紹。而對(duì)于結(jié)構(gòu)信息的計(jì)算，很多算法引入了傳統(tǒng)信息檢索(Information Retrieval，IR)的思路，其代表有Xrank、Xseek等。目前，屬于此類的查詢語言有很多種，包括：Lorel