相對(duì)解析分層遞歸關(guān)系

遞歸關(guān)系是序列的項(xiàng)之間的一種關(guān)系。指序列的任一項(xiàng)均被其前若干項(xiàng)所確定的那種關(guān)系。對(duì)于數(shù)列{a_n|n=0，1，2，…}，若當(dāng)n≥0時(shí)，恒有關(guān)系式：

a_{n k}=F(a_{n k-1}，…，a_n)，

這里k為正整數(shù)，F(xiàn)為元a_{n k-1}，…，a_n的代數(shù)函數(shù)，且a_n必在式中出現(xiàn)，則a_{n k}=F(a_{n k-1}，…，a_n)稱為數(shù)列{a_n|n=0，1，2，…}的一個(gè)逆歸關(guān)系。若給定此遞歸關(guān)系，且給出a₀，a₁，…，a_k-1的一組初值，則數(shù)列{a_n|n=0，1，2，…}完全確定。例如，遞歸關(guān)系a_{n 2}=a_{n 1} a_n及初值a₀=a₁=1完全確定數(shù)列1，1，2，3，5，8，…，稱為斐波那契數(shù)列。使用計(jì)算機(jī)，根據(jù)給定遞歸關(guān)系和初值計(jì)算相應(yīng)的數(shù)列的項(xiàng)很方便。因此，遞歸關(guān)系是研究數(shù)列的一個(gè)有力工具。

解析分層亦稱解析譜系。按照量詞復(fù)雜性對(duì)解析關(guān)系所作的遞歸論分層。與算術(shù)分層類似，任何解析關(guān)系可以用算術(shù)關(guān)系加上有窮個(gè)交替出現(xiàn)的二階函數(shù)量詞?′與?′表示，依照量詞個(gè)數(shù)，可以將該解析關(guān)系納入具體的解析分層Σ¹_n或π¹_n中。形式地，具體的解析分層Σ¹_n，π¹_n，Δ¹_n可遞歸定義如下：

1.Σ¹₀=π¹₀={R：R為算術(shù)關(guān)系}。

2.Σ¹_{n 1}={(?′f)R(f，f₁，f₂，…，f_k，x₁，x₂，…，x_m)：R∈π¹_n}.

3.π¹_{n 1}={(?′f)R(f，f₁，f₂，…，f_k，x₁，x₂，…，x_m)：R∈Σ¹_n}。

4.Δ¹_n=Σ¹_n∩π¹_n.

Σ¹_n，π¹_n與Δ¹_n中的關(guān)系分別稱為Σ¹_n關(guān)系、π¹_n關(guān)系與Δ¹_n關(guān)系，此外，Δ¹_w定義為：∪{Σ¹_n∪π¹_n：n∈ω}，即所有解析關(guān)系的集合。此外，對(duì)n≥1，Σ¹_n關(guān)系可表示成下形范式：

(?′f₁)(?′f₂)…(Q_nf_n)(Qx)

R(f₁，…，f_n，f_{n 1}，…，f_{n p}，x，x₁，…，x_q)，

其中若n為偶數(shù)，Q¹_n為?′，Q⁰為?⁰；若n為奇數(shù)，Q¹_n為?′，Q⁰為?⁰；而R為遞歸關(guān)系。π¹_n關(guān)系也可表示成以?′開頭的類似表達(dá)式.解析分層還具有如下封閉性：

1.Σ¹_n，π¹_n，Δ¹_n對(duì)合取、析取運(yùn)算與一階量詞封閉。

2.Δ¹_n對(duì)否定運(yùn)算封閉。

3.R∈Σ¹_n，當(dāng)且僅當(dāng)?R∈π¹_n；

R∈π¹_n，當(dāng)且僅當(dāng)?R∈Σ¹_n。

4.對(duì)n≥1，Σ¹_n對(duì)二階量詞?′封閉，π_n對(duì)二階量詞?′封閉。

關(guān)于解析分層的其他性質(zhì)，參見“解析枚舉定理”。此外，與算術(shù)分層不同，Δ¹₁≠Σ¹₀=π¹₀=Δ¹₀，Δ¹₁的關(guān)系稱為超算術(shù)關(guān)系。

相對(duì)解析分層(relativized analytical bierarchy)是解析分層概念的相對(duì)化。即對(duì)相對(duì)算術(shù)關(guān)系依量詞復(fù)雜性進(jìn)行的遞歸論分層。具體地，對(duì)自然數(shù)集A，相對(duì)A的解析分層Σ^1,A_n，π^1,A_n與Δ^1,A_n可遞歸定義如下：

1.Σ^1,A₀=π^1,A₀={R：R為相對(duì)A的算術(shù)關(guān)系}。

2.Σ^1,A_{n 1}={(?′f)R(f，f₁，f₂，…，f_k，x₁，x₂，…，x_m)：R∈π^1,A_n}。

3.π^1,A_{n 1}={(?′f)R(f，f₁，f₂，…，f_k，x₁，x₂，…，x_m)：R∈Σ^1,A_n}。

4.Δ^1,A_n=Σ^1,A_n∩π^1,A_n。

Σ^1,A_n，π^1,A_n與Δ^1,A_n中的關(guān)系分別稱為Σ^1,A_n關(guān)系，π^1,A_n關(guān)系與Δ^1,A_n關(guān)系。此外，用Δ^1,A_w表示∪{Σ^1,A_n∪π^1,A_n：n∈w}，即所有相對(duì)A的解析關(guān)系的集合。

算術(shù)關(guān)系是遞歸關(guān)系的推廣。是可以通過對(duì)遞歸關(guān)系添加有窮個(gè)量詞定義的關(guān)系，即可以表示Q₁x₁Q₂x₂…Q_nx_nR(x₁，x₂，…，x_n，a₁，a₂，…，a_n)形的關(guān)系，其中R為遞歸關(guān)系，Q₁，Q₂，…，Q_n為一階量詞?或?。等價(jià)地，算術(shù)關(guān)系亦是可以從遞歸關(guān)系出發(fā)，經(jīng)有限次否定與射影運(yùn)算得到的關(guān)系。算術(shù)關(guān)系的定義是由美國(guó)邏輯學(xué)家、數(shù)學(xué)家克林(Kleene，S.C.)與波蘭數(shù)學(xué)家莫斯托夫斯基(Mostowski，A.)給出的。

從可判定(或可計(jì)算)的角度上說，遞歸關(guān)系具有最小的復(fù)雜性，但遞歸關(guān)系對(duì)(不受限)量詞不封閉，而算術(shù)關(guān)系類則為遞歸關(guān)系類對(duì)量詞封閉的最小擴(kuò)張，因此算術(shù)關(guān)系的概念可看做遞歸關(guān)系概念的推廣。實(shí)際上，任何算術(shù)關(guān)系也恰為一階算術(shù)可定義關(guān)系，這也是“算術(shù)”一詞的來源。

算術(shù)關(guān)系概念的相對(duì)化。對(duì)自然數(shù)集A和關(guān)系R，若R可表示成(Q₁x₁)(Q₂x₂)…(Q_nx_n)S(x₁，x₂，…，x_n，a₁，a₂，…，a_m)的形式，其中Q₁，Q₂，…，Q_n為量詞?或?，S為相對(duì)A遞歸的關(guān)系，則稱R為相對(duì)于A的算術(shù)關(guān)系。若集合B是相對(duì)于A的(一元)算術(shù)關(guān)系，即B可表示成：{x：(Q₁y₁)(Q₂y₂)…(Q_ny_n)S(y₁，y₂，…，y_n，x)}其中Q₁，Q₂，…，Q_n為量詞，S為相對(duì)于A遞歸的n 1元關(guān)系，則稱B為相對(duì)于A的算術(shù)集，并記為B≤_aA，亦稱B可算術(shù)化歸到A。由算術(shù)化歸關(guān)系可導(dǎo)出算術(shù)等價(jià)的概念。對(duì)集合A，B，若A≤_aB，并且B≤_aA，則稱A，B算術(shù)等價(jià)，記為A≡_aB。2100433B

自動(dòng)數(shù)據(jù)分層（automated data tiering）是一種軟件程序，它根據(jù)公司規(guī)定的政策移動(dòng)分層存儲(chǔ)（tiered storage）間的數(shù)據(jù)文件、卷或區(qū)塊。

自動(dòng)數(shù)據(jù)分層（automated data tiering）是一種軟件程序，它根據(jù)公司規(guī)定的政策移動(dòng)分層存儲(chǔ)（tiered storage）間的數(shù)據(jù)文件、卷或區(qū)塊。

為了決定數(shù)據(jù)存儲(chǔ)的位置，自動(dòng)數(shù)據(jù)分層（automated data tiering）監(jiān)控?cái)?shù)據(jù)使用情況。頻繁訪問的數(shù)據(jù)會(huì)保留在高性能光纖通道（Fibre Channel）或是固態(tài)硬盤（solid-state drive）中，而低頻訪問的數(shù)據(jù)則被轉(zhuǎn)移到低成本、高容量的本地驅(qū)動(dòng)或是云存儲(chǔ)中。

廠商聲稱，自動(dòng)數(shù)據(jù)分層（automated data tiering）帶來了多種好處。它能減少存儲(chǔ)分層間動(dòng)態(tài)分類和遷移數(shù)據(jù)時(shí)管理存儲(chǔ)所需的時(shí)間。通過把低頻訪問數(shù)據(jù)轉(zhuǎn)移到低成本驅(qū)動(dòng)，組織不僅能省下用于高性能驅(qū)動(dòng)的花費(fèi)，還能通過減輕負(fù)載來提高性能。另外，減少活動(dòng)文件的數(shù)據(jù)可以減少日常備份時(shí)間。2100433B