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

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

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

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