基于分割的超樹分解方法

王 濤, 王瑞芹, 李占山, 陳 超

(1. 長春工業(yè)大學(xué) 計算機(jī)科學(xué)與工程學(xué)院, 長春 130012；2. 吉林大學(xué) 符號計算與知識工程教育部重點(diǎn)實(shí)驗室, 長春 130012; 3. 吉林大學(xué) 計算機(jī)科學(xué)與技術(shù)學(xué)院, 長春 130012)

約束滿足問題(constraint satisfaction problem, CSP)[1]廣泛應(yīng)用于符號推理、 系統(tǒng)診斷、 配置和調(diào)度等問題中. 尋找一個約束滿足問題的解是NP難問題[1], 目前已有很多優(yōu)秀的CSP求解算法, 其中嵌入約束傳播技術(shù)[2]的回溯算法[3]是一種應(yīng)用較廣泛的CSP求解算法. 為了處理CSP問題的高復(fù)雜性, 已產(chǎn)生了許多CSP分解方法, 其中超樹分解是目前應(yīng)用較多的一種方法. 它把CSP的結(jié)構(gòu)表示成一個超圖. 超圖是一個圖的泛化, 每條邊都與一個變量集相關(guān)聯(lián). Gottlob等[4]提出了超圖的超樹寬度是對無環(huán)性的一個合適度量, 也是衡量對應(yīng)計算問題是否為易處理問題的重要指標(biāo). 超樹分解的寬度越小, 相應(yīng)問題的處理效率越高. 決定一個超樹分解的寬度是否為k是NP難題.

文獻(xiàn)[4]指出, 對一個固定值k, 可在多項式時間內(nèi)決定是否存在一個分解寬度為k的超樹分解, 并提出了k-decomp算法[4]. 該算法可以構(gòu)造一個極小寬度不大于k(k-bounded) 的超樹分解(若這樣的分解存在). 另一種計算極小寬度不大于k的超樹分解方法是opt-k-decomp算法[5-9], 它是目前唯一能在多項式時間內(nèi)精確構(gòu)造k-bounded超樹分解的算法, 但它即使對于小的超樹也需要大量的存儲空間和時間. Gottlob等[10]提出了一種基于回溯的超樹分解算法det-k-decomp, 結(jié)合了精確算法和啟發(fā)式算法的優(yōu)點(diǎn), 搜索空間和產(chǎn)生超樹分解的寬度均由固定上限k限定, 即它可通過設(shè)置足夠小的k找到具有極小寬度的超樹分解. 該方法可以在產(chǎn)生的超樹寬度和計算時間之間進(jìn)行平衡. Subbarayan等[11]提出了基于回溯的超樹分解算法, 并把部件同構(gòu)的概念應(yīng)用于算法中, 以加速算法的執(zhí)行. 此外還提出了HyperSpread Decomposition和Connected HyperTree Decomposition算法, 并給出了實(shí)驗結(jié)果, 證明了引入同構(gòu)概念后Connected HyperTree Decomposition算法的優(yōu)越性.

基于det-k-decomp算法思想, 本文把Sathiamoorthy的同構(gòu)概念引入到det-k-decomp算法中, 提出一種新的易處理的分解方法： 基于分割的超樹分解算法----sht-k-decomp.

1 定 義

一個約束滿足問題(CSP)是一個三元組(X,D,C), 其中:X是一個有限變量集;D是一個有限值域集;C是一個有限約束集. 有限值域di∈D是變量xi∈X的取值集合, 每個約束ci∈C都對應(yīng)一個X的子集si及一個關(guān)系ri, 其中ri是變量集si上的關(guān)系, 它限制了si中變量的取值范圍. 若給si中所有變量一個賦值, 這些賦值的組合滿足關(guān)系ri, 則稱約束ci是可滿足的. 一個CSP的解是對CSP中的所有變量賦值, 且這些賦值滿足CSP中的所有約束.

一個CSP(X,C,D)的超圖H是一個二元組(V,E), 其中:V是一個變量集, 對應(yīng)于CSP的變量集X;E為超邊的集合, 對E中的每個超邊ei, 對應(yīng)于CSP中的一個約束ci, 滿足ei=si. 此外, 令vars(K)=∪e(e∈k), 其中K是超邊集E的子集,K?E,

edges(L)={e|e∈E,e∩L≠?}, edgesvar(L)=vars(edges(L)),

其中L是變量集V的子集.

超圖H(V,E)的超樹是一個三元組(T,χ,λ), 其中T=(N,E)是一個樹,N是T中節(jié)點(diǎn)的集合. 對超樹T中的節(jié)點(diǎn)n∈N,χ(n)對應(yīng)超圖H中變量集V的一個子集,λ(n)對應(yīng)超圖H中超邊集E的一個子集, 即

χ(n)?V,λ(n)?E.

T的子樹

用root(T)表示T的根節(jié)點(diǎn),T(n)表示T以n為根節(jié)點(diǎn)的子樹.

一個超圖H(V,E)的超樹分解是一個超樹(T,χ,λ), 其中T=(N,E), 滿足如下條件[2]：

1) ?e∈E, ?n∈N滿足e?χ(n);

2) ?v∈V, 集合{n|n∈N,v∈χ(n)}可誘導(dǎo)出T的一個子樹;

3) ?n∈N,χ(n)?∪λ(n);

4) ?n∈N, ∪λ(n)∩χ(T(n))?χ(n).

超樹分解(T,χ,λ)的寬度為|λ(n)|, 其中n∈N是樹T中包含超邊數(shù)目最多的節(jié)點(diǎn). 一個超圖的超樹寬度是該超圖所有超樹分解寬度的最小值, 記為htw(H). 若一個超圖H的超樹寬度htw(H)≤k, 則稱超圖H是k-decomposable的. 圖1為一個超圖及其寬度為2的超樹分解.

對超圖H=(V,E), 若存在超邊e∈E, 滿足x,y∈(∪e)W, 集合V′?V是[W]-connected的, 且V′中任意兩個變量都關(guān)于W相鄰, 則稱變量x,y∈V關(guān)于變量集W?V相鄰. 若一個[W]-component是一個極大的[W]-connected變量集V′?VW, 則稱W為一個separator, 它對超圖的超樹分解十分重要. 本文用覆蓋相應(yīng)變量集的超邊集合表示separator和[separator]-component.

定義1[4]若對T中的每個節(jié)點(diǎn)r及r的每個子節(jié)點(diǎn)s都滿足以下條件, 則一個超圖的超樹分解(T,χ,λ)是規(guī)格化形式的:

1) 存在一個[χ(r)]-componentCr, 使得

χ(T(s))=Cr∪(χ(s)∩χ(r));

2)χ(s)∩Cr≠?, 其中Cr是滿足條件1)的[χ(r)]-component;

3) ∪λ(s)∩χ(r)?χ(s).

圖1 一個超圖及該超圖寬度為2的超樹分解示意圖Fig.1 Example of a hypergraph and its hypertree decompositon of width 2

定義2[10]令(T,χ,λ)為超圖的一個具有規(guī)格化形式的超樹分解, 且s為T中的一個節(jié)點(diǎn), 如果s滿足下列條件, 則稱s是極小標(biāo)識的:

1) 若s=root(T), 則|λ(s)|=1;

2)s的父節(jié)點(diǎn)為r(存在相應(yīng)[χ(r)]-componentCr滿足

χ(T(s))=Cr∪(χ(s)∩λ(r)),

且滿足對任意e∈χ(s),

∪edges(Cr)∩∪λ(r)?∪(λ(r){e})或(λ(r){e})∩edges(Cr)=?.

定義3[10]若一個超圖的超樹分解是規(guī)格化形式的, 且它的每個節(jié)點(diǎn)都是極小標(biāo)識的, 則該超圖的超樹分解是強(qiáng)規(guī)格化形式的.

引理1[10]對超圖H的任一個寬度為k的超樹分解, 都存在一個相應(yīng)強(qiáng)規(guī)格化形式寬度為k的超樹分解.

2 Det-k-decomp算法

由det-k-decomp算法得到超圖H的超樹分解(若存在)是強(qiáng)規(guī)格化形式的.

算法1det-k-decomp(H).

FailSeps∶=?;

SuccSeps∶=?;

HTree∶=decompCov(edges(H),?);

if HTree≠NULL then

HTree∶=expand(HTree);

endif

return HTree.

算法2decompCov(Edges,Conn).

if |Edges|≤kthen

HTree∶=getHTNode(Edges,∪Edges,?);

return HTree;

endif

BoundEdges∶={e∈edges(H)|e∩Conn≠?}

for each CovSep∈cover(Conn,BoundEdges) do

HTree∶=decompAdd(Edges,Conn,CovSep)

if HTree≠NULL then

return HTree;

endif

endfor

return NULL.

算法3decompAdd(Edges,Conn,CovSep).

InCovSep∶=CovSep∩Edges

if InCovSep≠? ork-|CovSep|>0 then

if InCovSep=? then AddSize∶=1

else AddSize∶=0

endif;

for each AddSep?Edges s.t.|AddSep|=AddSize

do

Separator∶=CovSep∪AddSep;

Components∶=separate(Edges,Separator);

if ?Comp∈Components.〈Separator,Comp〉?FailSeps then

Subtrees∶=decompSub(Components,Separator);

if Subtrees≠? then

Chi∶=Conn∪∪(InCovSep∪AddSep);

HTree∶=getHTNode(Separator,Chi,SubTrees)；

return Htree;

endif

endif

endfor

endif

return NULL.

算法4decompSub(Components,Separator).

Subtrees∶=?

for each Comp∈Components do

ChildConn∶=∪Comp∩∪Separator

if 〈Separator,Comp〉∈SuccSeps then

HTree∶=getHTNode(Comp,ChildConn,?)

else

HTree∶=decompCov(Comp,ChildConn);

if HTree=NULL then

FailSeps∶=FailSeps∪ {〈Separator,Comp〉};

return ?;

else

SuccSeps∶=SuccSeps∪{〈Separator,Comp〉};

endif

endif

Subtrees∶=Subtrees∪{HTree};

endfor

return Subtrees.

圖2 Det-k-decomp各過程間的調(diào)用關(guān)系Fig.2 Procedure calls of det-k-decomp

算法1中, 集合FailSeps和SuccSeps中的元素是一個二元組〈Separator,Comp〉(這里稱為待分解部件), 分別用于存放分解過程中分解失敗的待分解部件和分解成功的待分解部件. 這樣在分解過程中若已知當(dāng)前待分解部件可成功分解, 則把當(dāng)前待分解部件作為超樹的截止節(jié)點(diǎn)； 否則, 返回, 不繼續(xù)當(dāng)前分解. det-k-decomp是主過程, 調(diào)用decompCov,decompAdd和decompSub過程對超圖進(jìn)行分解, 并返回分解得到的超樹(若不存在, 返回空樹). 在算法1的最后, 對分解得到的超樹執(zhí)行expand函數(shù)擴(kuò)展分解過程中得到的截止節(jié)點(diǎn). 算法2～算法4是遞歸調(diào)用過程, 完成對超圖的分解. 各算法調(diào)用關(guān)系如圖2所示.

該算法中, 最重要的是separator的選擇. 對待分解超圖, 先選擇出作為分解基準(zhǔn)的separator, 再找出待分解超圖中所有的[separator]-component, 最后逐個迭代分解每個[separator]-component, 直到每個子超圖都分解為寬度不大于k的超樹為止.

每次選出的separator都應(yīng)滿足如下兩個基本條件:

1) ∪Edges∩∪OldSep?∪separator;

2) separator∩Edges≠?.

其中: Edges是待分解超圖(這里用超圖的超邊集合表示超圖); OldSep是上次選出的separator. 算法4先對Childconn=∪Edges∩∪OldSep進(jìn)行計算, 然后把Childconn作為參數(shù)傳遞給算法2. 算法2在超圖中尋找與Conn(即Childconn)有共同變量的所有超邊, 存放在集合BoundEdges中. 這樣BoundEdges集合中就存放了所有與∪separator有交集的超邊, 并且∪BoundEdges=∪separator. 因此, 可以考慮將超邊集合BoundEdges中的超邊作為separator, 以縮減separator的搜索空間. 首先, 從BoundEdges中選出一個最多有k個超邊的子集CovSep, 使得Conn?∪CovSep, 且CovSep?separator. 該選擇過程由Cover函數(shù)完成. Cover過程可返回所有的CovSep. 然后調(diào)用算法3, 在decompAdd過程中首先判斷CovSep是否與待分解超圖Edges有交集, 且是否|separator|≤k決定separator的最終取值, 得到的separator即滿足上述兩個基本條件.

選出滿足條件的separator后, 在算法3中調(diào)用separate函數(shù), 對待分解超圖Edges進(jìn)行分解, 并將分解得到的每個子超圖Comp, 即[separator]-component, 放入集合components中. 然后判斷components中是否存在已知不可分解的Comp, 若存在, 則重新選擇separator； 否則, 調(diào)用decompSub過程對components中的所有Comp進(jìn)行分解, 并調(diào)用getHTNode函數(shù)構(gòu)造當(dāng)前超樹節(jié)點(diǎn), 其中: Chi為此節(jié)點(diǎn)的χ標(biāo)識; Separator為節(jié)點(diǎn)的λ標(biāo)識; Subtrees為當(dāng)前節(jié)點(diǎn)的子樹集合.

算法4完成對當(dāng)前分解得到的各個子超圖的分解. 對每個子超圖, 先計算出其與當(dāng)前分解選出的separator的交集： Childconn作為分解該子超圖時選擇separator的依據(jù); 再判斷當(dāng)前子超圖是否已知可以成功分解, 若可以, 則把當(dāng)前部件作為截止節(jié)點(diǎn); 否則調(diào)用遞歸過程decompCov進(jìn)行分解; 根據(jù)分解結(jié)果把當(dāng)前部件存放到FailSeps或SuccSeps中; 最后返回分解得到的子樹, decompSub過程結(jié)束.

在det-k-decomp算法中, Cover過程應(yīng)用了一種啟發(fā)式, 即首先按超邊中包含的Conn中變量的個數(shù)給BoundEdges中的每條超邊賦一個權(quán)值, 然后根據(jù)該權(quán)值, 從大到小進(jìn)行排序, 最后基于這個順序, 選擇出所有可覆蓋Conn的極小超邊集CovSep.

由算法2可見, 在計算BoundEdges時, 是從超圖的所有超邊中選取. 但在許多超圖例子中可以注意到： 對兩個[OldSep]-component Edges和Edges′, ∪Edges∩∪OldSep∩∪Edges′≠?, 這樣在對Edges進(jìn)行分解時, 選取的separator可能會包含Edges′中的超邊. 在多數(shù)情況下, Edges′的超邊對Edges的分解沒有實(shí)際作用, 甚至有時Edges′中超邊的選取還會導(dǎo)致該次循環(huán)過程的失敗返回. 因此, 本文提出了分割的超樹分解----SHTD的概念.

3 分割的超樹分解

定義4一個超圖的分割的超樹分解SHTD=(T,χ,λ), 滿足如下條件：

1) 它是一個具有強(qiáng)規(guī)格化形式的超樹分解;

2) 若對T中的每個節(jié)點(diǎn)r和r的子節(jié)點(diǎn)集合S, 滿足?si,sj∈S, 有

λ(si)∩λ(sj)?∪λ(r).

條件2)表明在選取下一個separator時, 只從OldSep和待分解的Edges中選取, 而不是從所有的超邊中選取.

對det-k-decomp算法進(jìn)行時間復(fù)雜度分析可知, 算法的時間主要是由decompCov算法的循環(huán)次數(shù)決定, 因此對BoundEdges集合的大小進(jìn)行限制, 可減少InCover過程返回滿足條件的CovSep數(shù)目, 進(jìn)而減少CovSep的循環(huán)次數(shù), 降低時間復(fù)雜度. 令超圖H的分割的超樹寬度為shtw(H), 可知htw(H)≤shtw(H). 若shtw(H)≤k, 則稱超圖H是s-k-decomposable的. 由于分割的超樹分解是超樹分解的一個子集, 因此分割的超樹分解也是可處理的.

文獻(xiàn)[8]中提出了同構(gòu)的概念, 在其回溯的超樹分解算法中, 待分解部分Comp是一個變量的集合, 而在det-k-decomp中則把該待分解部分Comp轉(zhuǎn)化為edges(Comp), 這兩種情況是等價的, 且

Comp=∪edges(Comp)∪OldSep.

若Comp=Comp′, 則稱(OldSep,Comp)和(OldSep′,Comp′)是同構(gòu)的. 文獻(xiàn)[8]還證明了

Conn=∪edges(Comp)∩∪OldSep=∪edges(Comp)Comp

的選取與OldSep無關(guān). 因為BoundEdges的取值是從所有超邊中選取, 所以separator的選取也只與Conn和Comp有關(guān), 與OldSep無關(guān). 因此, 同構(gòu)的兩個部件可分解性也是等價的. 引入同構(gòu)的概念, 可使遞歸運(yùn)算極大減少.

基于上述分析, 本文提出基于分割的超樹分解算法----sht-k-decomp算法. 該算法基于det-k-decomp算法思想, 并引入同構(gòu)的概念, 舍棄一些對分解失敗概率較大的子超圖分解, 使分解效率得到提高. 需注意的是sht-k-decomp算法得到的超樹分解并不一定是分割的超樹分解.

4 Sht-k-decomp算法

算法5Sht-k-decomp(edges(H)).

FailSeps∶=?;

SuccSeps∶=?;

HTree∶=SdecompCov(vars(edges(H)),?,?);

if HTree≠NULL then

HTree∶=expand(HTree);

endif

return HTree.

算法6SdecompCov(Comp,Conn,OldSep).

if |edges(Comp)|≤kthen

HTree∶=getHTNode(edges(Comp),∪edges(Comp),?);

return HTree;

endif

InBoundEdges∶={e∈edges(Comp)∪OldSep|e∩Conn≠?}

for each CovSep∈Cover(Conn,InBoundEdges) do

HTree∶=SdecompAdd(Comp,Conn,CovSep,OldSep)

if HTre≠NULL then

return HTree;

endif

endfor

return NULL.

算法7SdecompAdd(Comp,Conn,CovSep,OldSep).

InCovSep∶=CovSep∩edges(Comp)

if InCovSep≠? ork-|CovSep|>0 then

if InCovSep=? then AddSize∶=1

else AddSize∶=0

endif;

for each AddSep?edges(Comp) s.t.|AddSep|=AddSize do

Separator∶=CovSep∪AddSep;

Components∶=separate(Comp,Separator);

if ?SepComp∈Components.

〈Separator,SepComp〉?FailSeps then

Subtrees∶=SdecompSub(Components,Separator,OldSep);

if Subtrees≠? then

Chi∶=Conn∪∪(InCovSep∪AddSep);

HTree∶=getHTNode(Separator,Chi,Subtrees);

return Htree;

endif

endif

endfor

endif

return NULL.

算法8SdecompSub(Components,separator,OldSep).

Subtrees∶=?

for each Comp∈Components do

ChildConn∶=∪edges(Comp)∩∪separator

if Comp∈SuccSeps then

HTree∶=getHTNode(Comp,ChildConn,?)

else

HTree∶=SdecompCov(Comp,ChildConn,separator);

if HTree=NULL then

FailSeps∶=FailSeps∪{〈OldSep,Comp〉};

return ?;

else

SuccSeps∶=SuccSeps∪{Comp};

endif

endif

Subtrees∶=Subtrees∪{HTree};

endfor

return Subtrees.

本文算法基于det-k-decomp算法思想, 不同之處在于： 在sht-k-decomp算法中, 待分解部件是一個變量集合Comp, 而不是超邊集合； 對separator的選擇空間做了進(jìn)一步限制, 主要體現(xiàn)在對與變量集Conn有公共變量的超邊集(det-k-decomp算法中此集合為BoundEdges; sht-k-decomp算法中為InBoundEdges)的計算上. 此外, 在sht-k-decomp算法中本文引入了同構(gòu)概念. 但在sht-k-decomp算法中, InBoundEdges的取值是與OldSep有關(guān)的, 所以separator的選取也與OldSep相關(guān). 因此, 在sht-k-decomp算法中判斷是否已知不為k-decomposable時, 就需要判斷〈OldSep,Comp〉是否屬于FailSeps, 而在判斷是否已知是k-decomposable時, 可引入Sathiamoorthy的同構(gòu)概念, 即只需判斷〈comp〉是否與SuccSeps中的部件同構(gòu), 但這樣得到的超樹分解不一定是SHTD.

令由算法sht-k-decomp得到的超樹分解寬度為sdhtw(H), 則htw(H)≤sdhtw(H).

定理1Sht-k-decomp返回一個基于分割的超樹分解當(dāng)且僅當(dāng)sdhtw(H)≤k.

證明： sht-k-decomp是在det-k-decomp基礎(chǔ)上進(jìn)行改進(jìn)的. 與det-k-decomp算法相同, sht-k-decomp是一個迭代過程, 在每次迭代中, 它會循環(huán)所有可能的分解情況, 即循環(huán)滿足條件的separator并進(jìn)行分解, 直到成功返回一個分解寬度至多為k的分割超樹分解或在迭代循環(huán)完所有的separator后返回一顆空樹. 因此, 若存在sdhtw(H)≤k的分割超樹分解, sht-k-decomp過程則一定能找到這樣的超樹分解, 并成功返回.

表1列出了分別使用det-k-decomp算法和sht-k-decomp算法對圖1中超圖進(jìn)行分解的對比結(jié)果.

表1 Det-k-decomp和sht-k-decomp分解過程對比

由表1可見, 當(dāng)Conn={a,c,d}時, det-k-decomp算法中計算得到的

BoundEdges={A,B,C,D,E,F},

其Cover函數(shù)可返回的CovSep順序為{B,C},{A,B},{B,F},{C,E},{C,D},{A,E},{E,F}. 而對sht-k-decomp算法, 計算得到的InBoundEdges={B,E,A,F}, Cover函數(shù)可返回的CovSep順序為{A,B},{B,F},{A,E},{E,F}. 對超圖的分解, sht-k-decomp中會避免det-k-decomp中因CovSep取{B,C}而導(dǎo)致分解失敗的情況. 這是較小的例子, 對較大的例子, 超邊越多, 這種情況出現(xiàn)的幾率就越大, 此時用sht-k-decomp會極大提高分解效率.

5 實(shí)驗結(jié)果

本文使用文獻(xiàn)[10]中的部分測試用例對det-k-decomp算法和sht-k-decomp算法進(jìn)行對比. 測試環(huán)境為硬件DELL Intel Core 2 Duo 2.93 GHz CPU/2.0 Gb RAM； 軟件Windows XP Professional SP2/Visual C++6.0. 每個用例測試10次, 取平均值作為最后結(jié)果.

在測試用例時, 本文設(shè)置時間限制為3 600 s, 并令k為不大于從det-k-decomp算法中已得到的最小分解寬度的值. 實(shí)驗結(jié)果列于表2和表3. 表2和表3為在時間限制范圍內(nèi)得到的測試結(jié)果, 其中|V|和|E|分別為待分解超圖包含的變量數(shù)和超邊數(shù). 對這兩個算法, 用兩組屬性進(jìn)行比較： 運(yùn)行時間和最小分解寬度, 并把分解寬度作為最重要的對比標(biāo)準(zhǔn). 在最小分解寬度相同的條件下, 運(yùn)行時間越少, 算法運(yùn)行效率越高.

表2 DaimlerChrysler和Grid2D標(biāo)準(zhǔn)庫測試用例

表3 ISCAS89標(biāo)準(zhǔn)庫測試用例

由表2和表3可見, 對所有例子, sht-k-decomp算法得到的最小分解寬度與det-k-decomp算法的最小分解寬度相同, 且多數(shù)情況下sht-k-decomp算法的執(zhí)行效率高于det-k-comp算法.

綜上所述, 本文提出了一種新的超樹分解方法： 分割的超樹分解----SHTD, 并基于分割的超樹分解所具有的特征提出了一種新的超樹分解算法----基于分割的超樹分解算法sht-k-decomp. 分割的超樹分解是超樹分解的子集, 它較易處理且htw(H)≤shtw(H). 算法sht-k-decompc通過進(jìn)一步縮小separator的搜索空間和引入同構(gòu)概念對算法det-k-decomp進(jìn)行改進(jìn). 采用文獻(xiàn)[10]部分用例進(jìn)行測試, 結(jié)果表明在多數(shù)情況下, sht-k-decomp算法高于det-k-decomp算法的效率, 且對所有的例子它們的最優(yōu)分解寬度相同.

[1] Freuder E C, Mackworth A K. Constraint Satisfaction: An Emerging Paradigm [C]//Handbook of Constraint Programming. Amsterdan: Elsevier, 2006: 13-27.

[2] Bessière C. Constraint Propagation [C]//Handbook of Constraint Programming. Amsterdan: Elsevier, 2006: 29-84.

[3] Beek P, Van. Backtracking Search Algorithms [C]//Handbook of Constraint Programming. Amsterdan: Elsevier, 2006: 85-134.

[4] Gottlob G, Leone N, Scarcello F. Hypertree Decompositions and Tractable Queries [J]. Journal of Computer and System Sciences, 2002, 64(3): 579-627.

[5] Gottlob G, Leone N, Scarcello F. On Tractable Queries and Constraints [C]//Proceedings of the 10th International Conference on Database and Expert System Applications (DEXA). London: Springer-Verlag, 1999: 1-15.

[6] Leone N, Mazzitelli A, Scarcello F. Cost-Based Query Decompositions [C]//Proceedings of the 10th Italian Symposium on Advanced Database Systems (SEBD). Portoferraio: [s.n.], 2002: 390-403.

[7] Scarcello F, Greco G, Leone N. Weighted Hypertree Decompositions and Optimal Query Plans [J]. Journal of Computer and System Sciences, 2007, 73(3): 475-506.

[8] Gottlob G, Leone N, Scarcello F. A Comparison of Structural CSP Decomposition Methods [J]. Artificial Intelligence, 2000, 124(2): 243-282.

[9] Harvey P, Ghose A K. Reducing Redundancy in the Hypertree Decomposition Scheme [C]//Proceedings of the 15th International Conference on Tools with Artificial Intelligence. LosAlamitos, CA: IEEE Computer Society, 2003: 474-481.

[10] Gottlob G, Samer M. A Backtracking-Based Algorithm for Hypertree Decomposition [J]. Journal of Experimental Algorimics (JEA), 2008, 13(1): Article No.1.

[11] Subbarayan S, Andersen H R. Backtracking Procedures for Hypertree, HyperSpread and Connected Hypertree Decomposition of CSPs [C]//Proceedings of the 20th International Joint Conference on Artificial Intelligence. Hyderabad, India: [s.n.], 2007: 180-185.