科學(xué)工作流中的正則查詢(xún)與關(guān)鍵字檢索技術(shù)研究.pdf

1、隨著計(jì)算機(jī)技術(shù)的日新月異和自然科學(xué)領(lǐng)域的不斷發(fā)展，科學(xué)工作流作為面向數(shù)據(jù)的工作流旨在利用計(jì)算機(jī)技術(shù)幫助人們解決科學(xué)實(shí)驗(yàn)的數(shù)據(jù)再現(xiàn)和有效性驗(yàn)證等問(wèn)題，并進(jìn)一步減輕科學(xué)實(shí)驗(yàn)設(shè)計(jì)與分析的人力成本。作為一個(gè)剛剛起步的新研究領(lǐng)域，需要探索其具體應(yīng)用場(chǎng)景，歸納應(yīng)解決的實(shí)際問(wèn)題。
　　本文正是在這種背景下，調(diào)研問(wèn)題的應(yīng)用場(chǎng)景與實(shí)際需求，從最基本的科學(xué)工作流建模開(kāi)始，研究科學(xué)工作流中數(shù)據(jù)起源正則查詢(xún)與關(guān)鍵字檢索的若干關(guān)鍵問(wèn)題。一方面，現(xiàn)有科學(xué)工作

2、流中數(shù)據(jù)起源研究停留在可達(dá)性查詢(xún)階段，主要回答“某數(shù)據(jù)點(diǎn)d1是否依賴(lài)于數(shù)據(jù)點(diǎn)d2?”等類(lèi)似問(wèn)題。本文研究更為復(fù)雜的查詢(xún)——正則查詢(xún)，回答諸如“某數(shù)據(jù)點(diǎn)d1是否經(jīng)過(guò)技術(shù)a1或者技術(shù)a2重復(fù)處理過(guò)，然后由技術(shù)s處理過(guò)的，最終輸出數(shù)據(jù)d2?”等問(wèn)題，這個(gè)查詢(xún)可以由正則查詢(xún)R=(a1|a2)*.s.(_)*表征。另一方面，科學(xué)工作流中的關(guān)鍵字檢索不同于普通的文本檢索，需要考慮科學(xué)工作流模式構(gòu)建科學(xué)工作流運(yùn)行實(shí)例的表征能力?？茖W(xué)工作流中的關(guān)鍵字檢

3、索是對(duì)科學(xué)工作流模式共享庫(kù)進(jìn)行檢索?？茖W(xué)工作流模式庫(kù)中科學(xué)工作流模式的每個(gè)模塊（包括復(fù)雜模塊與原子模塊）都由一個(gè)或多個(gè)關(guān)鍵字標(biāo)注。當(dāng)用戶(hù)需要設(shè)計(jì)新的科學(xué)工作流時(shí)，可以通過(guò)輸入關(guān)鍵字對(duì)科學(xué)工作流模式共享庫(kù)進(jìn)行檢索，進(jìn)而可以重用部分共享庫(kù)中已有科學(xué)工作流模式或模塊，從而減輕實(shí)驗(yàn)設(shè)計(jì)的人力成本。
　　本文對(duì)自然科學(xué)領(lǐng)域科學(xué)實(shí)驗(yàn)中遇到的實(shí)際問(wèn)題進(jìn)行調(diào)研分析，在此基礎(chǔ)上，結(jié)合數(shù)據(jù)管理技術(shù)，對(duì)科學(xué)工作流中的正則查詢(xún)和關(guān)鍵字檢索兩大問(wèn)題進(jìn)行深入

4、研究，主要貢獻(xiàn)和創(chuàng)新包括:
　　第一，提出基于上下文無(wú)關(guān)包文法的科學(xué)工作流模型?；谏舷挛臒o(wú)關(guān)文法的科學(xué)工作流模型使用文法表征科學(xué)工作流模式，文法的語(yǔ)言對(duì)應(yīng)科學(xué)工作流運(yùn)行實(shí)例。上下文無(wú)關(guān)圖文法用以描述科學(xué)工作流中的數(shù)據(jù)依賴(lài)關(guān)系并用于進(jìn)行數(shù)據(jù)起源的正則查詢(xún)。而上下文無(wú)關(guān)包文法通過(guò)將科學(xué)工作流模塊的關(guān)鍵字建模到文法的產(chǎn)生式中，使得關(guān)鍵字檢索更為簡(jiǎn)潔，關(guān)鍵字匹配的語(yǔ)義更為清晰。
　　第二，提出一種基于節(jié)點(diǎn)編碼的科學(xué)工作流數(shù)據(jù)起源正

5、則查詢(xún)方法。本文提出的正則查詢(xún)方案基于一類(lèi)特殊查詢(xún)——穩(wěn)定正則查詢(xún)。將點(diǎn)對(duì)點(diǎn)穩(wěn)定查詢(xún)的時(shí)間復(fù)雜度降低到常數(shù)級(jí)，是最優(yōu)算法;將多點(diǎn)穩(wěn)定查詢(xún)的時(shí)間復(fù)雜度做到僅與輸入節(jié)點(diǎn)表的大小有關(guān)而與數(shù)據(jù)起源圖的大小無(wú)關(guān)，附加地將多點(diǎn)可達(dá)查詢(xún)的時(shí)間復(fù)雜度降低到線(xiàn)性于輸入輸出，是最優(yōu)算法;最后本文將穩(wěn)定正則查詢(xún)擴(kuò)展到通用正則查詢(xún)，顯著地提升了查詢(xún)效率。
　　第三，提出一種新型的科學(xué)工作流關(guān)鍵字檢索方案。本文定義了科學(xué)工作流中關(guān)鍵字檢索的匹配語(yǔ)義，并將上