約束關(guān)系模型的查詢(xún)包含問(wèn)題在實(shí)際數(shù)據(jù)庫(kù)中的不可判定的研究.pdf

1、查詢(xún)包含問(wèn)題是查詢(xún)優(yōu)化的基本算法問(wèn)題。在數(shù)據(jù)庫(kù)理論方面,約束關(guān)系模型的不等式合取查詢(xún)包含問(wèn)題已經(jīng)得到解決。然而,由于數(shù)據(jù)庫(kù)理論與實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)存在較大差異,十多年來(lái),實(shí)際數(shù)據(jù)庫(kù)系統(tǒng)中的合取查詢(xún)包含問(wèn)題的求值復(fù)雜性已經(jīng)成為一個(gè)熱點(diǎn)問(wèn)題,目前,這個(gè)問(wèn)題是否是可判定的還不得而知。本文根據(jù)約束關(guān)系模型在數(shù)據(jù)庫(kù)理論方面取得的成就,研究實(shí)際數(shù)據(jù)庫(kù)系統(tǒng)中約束關(guān)系模型的不等式合取查詢(xún)包含問(wèn)題是否是可判定的。 本文采用關(guān)系演算來(lái)表示查詢(xún)。首先,

2、通過(guò)關(guān)系演算的變換表明數(shù)據(jù)庫(kù)理論與實(shí)際數(shù)據(jù)庫(kù)系統(tǒng)之間存在的差異。然后,將一般的合取查詢(xún)包含問(wèn)題轉(zhuǎn)化為二元約束關(guān)系的合取查詢(xún)包含問(wèn)題。最后,將Hilbert第十問(wèn)題遞歸地化簡(jiǎn)為二元約束關(guān)系的合取查詢(xún)包含問(wèn)題,以此得出本文的主要結(jié)論。本文引入含有系數(shù)為非負(fù)整數(shù)的多項(xiàng)式描述Hilbert第十問(wèn)題,然后,構(gòu)造一類(lèi)特殊的數(shù)據(jù)庫(kù),使Hilbert第十問(wèn)題可以遞歸地化簡(jiǎn)為這類(lèi)特殊數(shù)據(jù)庫(kù)上的查詢(xún)包含問(wèn)題,再適當(dāng)?shù)匦拚懊嬗玫降牟樵?xún),使上述問(wèn)題適用于任意

3、的數(shù)據(jù)庫(kù)系統(tǒng)。 研究表明：不能將約束關(guān)系模型在數(shù)據(jù)庫(kù)理論查詢(xún)優(yōu)化中所取得的研究成果直接轉(zhuǎn)化到實(shí)際數(shù)據(jù)庫(kù)系統(tǒng)中。通過(guò)進(jìn)一步的研究本文得出更強(qiáng)的結(jié)論：一般情況下,實(shí)際數(shù)據(jù)庫(kù)系統(tǒng)中二元約束關(guān)系的不等式合取查詢(xún)包含問(wèn)題不可判定,甚至在將不等式的總數(shù)限定為一個(gè)固定的值時(shí),該問(wèn)題仍然不可判定。這種強(qiáng)烈的不可判定性表明：在實(shí)際的數(shù)據(jù)庫(kù)系統(tǒng)中,用二元約束關(guān)系的不等式合取查詢(xún)包含問(wèn)題作為工具來(lái)優(yōu)化查詢(xún)操作是不可能的。但是,如果將含有不等式的合取查