李婷婷

摘要：該文簡單介紹了一種新的數(shù)據(jù)庫概化方法，其主要貢獻是在邏輯語言的描述基礎(chǔ)上，給出一種通用的方法，對數(shù)據(jù)庫的模式和內(nèi)容都能起到作用。概化的過程將導致概化晶格的生成，并且每個都給出了精度的特定量度。

關(guān)鍵詞：數(shù)據(jù)庫概化；邏輯描述；概化晶格；數(shù)據(jù)庫模式；概化過程

中圖分類號：TP311 文獻標識碼：A 文章編號：1009-3044（2014）14-3217-03

Abstract：In this paper， we propose a new approach of database summarization. The main contribution of our work consists in giving a generic approach， based on description logic language， which operates on both the schema and the database content. The summarization process leads to building a lattice of summaries where each one gives a certain measure of precision.

Key words： database summarization； description logic； summaries lattice； database schema； summaries process

1 概述

隨著數(shù)據(jù)庫規(guī)模的日益發(fā)展，管理和提取大量的數(shù)據(jù)面臨著越來越多的困難。因此，提出一種方法，其能通過數(shù)據(jù)庫概化的發(fā)展為用戶提供簡潔易懂的數(shù)據(jù)陳述，是非常有意義的。該文旨在提出一種基于描述邏輯理論的新的數(shù)據(jù)概化方法，并在下文作簡要陳述。

2 相關(guān)工作

關(guān)于如何減小數(shù)據(jù)庫規(guī)模，主要可以分為四類：基于一元運算符的方法（垂直和水平減少）；涉及到多維數(shù)據(jù)庫的方法，如OLAP和QuotientCube；基于統(tǒng)計和符號技術(shù)的方法；基于模糊集合理論的方法[1，2，3]。

這些方法雖然能有效地減少數(shù)據(jù)庫規(guī)模，但是也存在不可忽視的缺點。隨著數(shù)據(jù)量迅速降低，已獲得的概化很少包含層次化信息和演繹信息；主要是對元組工作而不是整個數(shù)據(jù)庫；雖然現(xiàn)有的方法都是使用到模糊集合技術(shù)，但并不是所有的都能帶來顯著的結(jié)果[4，5]。

本文基于邏輯描述，對概化給出不同的觀點和方法，上面提到的這些技術(shù)可以被看作本文概化方法的特例。

3 數(shù)據(jù)庫概化

3.1 基本假設(shè)

在整篇文章里，我們假設(shè)數(shù)據(jù)庫是由UML類圖給出，其中包含類和關(guān)系。數(shù)據(jù)庫B可以表示為一個三元組，其中，I指定數(shù)據(jù)庫的intension，可以由一組{C1，C2，...，Ci，...，Cn}來表示，n，i∈N（自然數(shù)），Ci∈C（所有可能的類）。每個類是由一組屬性{A1，A2，...， Ai，...，An}定義，n，i∈N并且Ai∈A（類屬性），其中每個屬性都有一個域DA。注意，DA指定屬性的所有值，既可以是定量的也可以是定性的。R表示關(guān)系{R1，R2，...，Ri，...，Rm}，m，i∈N，R∈R（所有可能的關(guān)系）。I和R表示數(shù)據(jù)庫模式。E表示extension，其代表了所有類的實例（即數(shù)據(jù)庫元組）。

3.2 定義數(shù)據(jù)庫概化

數(shù)據(jù)庫概化可以被定義為一組結(jié)構(gòu)化數(shù)據(jù)的簡單表示[6]。其可以從三方面入手：數(shù)據(jù)庫模式以及涉及他們之間的類和關(guān)系；數(shù)據(jù)庫屬性；數(shù)據(jù)庫元組。

這里，我們強調(diào)，概化一個數(shù)據(jù)庫并不意味著一定要減少類或?qū)傩缘臄?shù)量，也有可能創(chuàng)造新的類或?qū)傩浴?/p>

注意，數(shù)據(jù)庫概化方法必須同時在結(jié)構(gòu)和內(nèi)容進行上操作，在意義上必須是通用的，并且獨立于數(shù)據(jù)庫模型，這也解釋了將UML類圖作為初始數(shù)據(jù)庫結(jié)構(gòu)的原因。

4 數(shù)據(jù)庫概化方法的概述

數(shù)據(jù)庫概化同時涉及模式，類屬性和實例，為此，我們需要解決的主要問題之一是如何同時處理數(shù)據(jù)庫模式和實例，我們希望能夠找到一種通用的形式體系，用來合并extension和intention。

4.1 邏輯描述數(shù)據(jù)庫

描述邏輯（DL）是一種常規(guī)描述語言，DL對術(shù)語（TBOX）和斷言描述（ABOX）加以區(qū)別。 TBOX包含了概念層次結(jié)構(gòu)和它們之間關(guān)系的描述，而ABOX則詳細描述了層次結(jié)構(gòu)中的個體實例。下面，我們將詳細講述TBOX和ABOX與我們案例的研究。

4.1.1 TBOX

TBOX包含了它們之間不同的類和可能的關(guān)系的定義，如下：

概念：Class <= T（頂層概念）

MotherClass= Class∩[?]generalise.Class

關(guān)系：歸納，關(guān)聯(lián)，聚集，... 。該列表并不詳盡，我們只給了一些樣本加以解釋，將我們的數(shù)據(jù)庫模式轉(zhuǎn)換為邏輯表達式。

4.1.2 ABOX

一旦所有的概念和關(guān)系被指定，我們像圖1一樣為斷言進行定義：

Class （Circle）

Class （Shape）

generalize （Circle， Shape）

根據(jù)TBOX的定義，可以推理得出Shape是一個MotherClass。為了能夠在邏輯描述中有效地表達數(shù)據(jù)庫，我們使用Web本體語言O(shè)WL DL，上述例子的OWL描述如下：

一旦數(shù)據(jù)庫模式和實例在邏輯描述中被指定，為了概化，一些規(guī)則就會被定義用來轉(zhuǎn)換數(shù)據(jù)庫。

4.2 數(shù)據(jù)庫轉(zhuǎn)換

如上所述，數(shù)據(jù)庫在描述邏輯語言時需要正式化，這樣其模式和實例就可以通過邏輯表達式來表示。因此，概化是一組新的邏輯表達式，其可以從原有的數(shù)據(jù)庫中導出。數(shù)據(jù)庫轉(zhuǎn)換包括很多方面：數(shù)據(jù)庫重組，屬性減少或分組以及實例的減少。事實上，我們可以為概化定義歸類，它表示一個層次關(guān)系，前類將被通用的類來代替，比如，圖1中類Circle將由類Shape代替。

關(guān)于屬性，需要考慮兩種可能性。第一，每個屬性都有一定的權(quán)重（由將來的數(shù)據(jù)庫用戶分配），表明有關(guān)的屬性是上下文相關(guān)的；第二，我們使用聚類算法，為具有一定接近度的屬性分組，在這種情況下，我們還可以定義一個與屬性權(quán)重相關(guān)的參數(shù)。

關(guān)于實例，我們使用符號數(shù)據(jù)技術(shù)來描述具有復雜和多值數(shù)據(jù)的元組。例如，對數(shù)值類型的屬性值進行概化，需要定義區(qū)間類型的符號對象，其邊界可以使用屬性的最小和最大值。在標稱類型屬性情況下，則需要生成一個符號對象，它是所有的屬性標稱值的集合。為了說明這一點，我們考慮下面的數(shù)據(jù)庫，其中包含類Circle的元組（表1）：

第一種概化方法是根據(jù)顏色的不同分，半徑值被替換為一個符號對象，它是一個區(qū)間，其中邊界表示半徑的最小值和最大值，如表2所示。

根據(jù)表3所示的半徑值，相同的元組可以有不同的概化。當然，我們也可以有其他結(jié)合，這取決于使用者的需求。

應(yīng)用上面介紹的轉(zhuǎn)換，一個數(shù)據(jù)庫可以產(chǎn)生不同的概化結(jié)果。下面，我們證明可以將所獲得的概化在晶格結(jié)構(gòu)中進行組織。

4.3 生成概化晶格

我們用S和使不同概化相互聯(lián)系的歸類Sub表示指生成的概化，把P（S）作為部分概化結(jié)果：P（S）={Si/Si[∈]S}，且S1，S2，S3三個概化均包含在S中，Sub有如下性質(zhì)：

反身性：?S1[∈]P（S） ： S1≤S1

對稱性： ?S1[∈]P（S） ， ?S2[∈]P（S） ： S1≤ S2 and S2≤S1? S1 = S2

傳遞性： ?S1， S2， S3[∈]P（S）3 ： S1≤S2 and S2≤S3 ?S1≤ S3

所以，Sub定義了一個偏序集，（P（S），Sub）定義了一個晶格。它有一個上界和下界，其中上界是初始的數(shù)據(jù)庫，下界是空集。

5 數(shù)據(jù)庫概化性能

我們大體上可以分為兩種標準：信息性和一致性。它們是成反比的，概化的越詳細，就越不一致。信息性測量了信息通過概化如何被給出，一致性了衡量了定義數(shù)據(jù)庫粒度所需的數(shù)據(jù)量。信息性與一致性的結(jié)合可以被視為選擇一個特定概化精度的標準。

6 結(jié)束語

在本文中，我們提出了基于描述邏輯的方法來建立數(shù)據(jù)庫概化晶格。我們的提議總共分三步：首先，使用描述邏輯（DL）語言正式化數(shù)據(jù)庫；其次，給原始數(shù)據(jù)庫的簡化定義規(guī)則，這些規(guī)則可用于減小模式，屬性和數(shù)據(jù)庫的實例。它并不是單一地簡化數(shù)據(jù)庫，它也可以在數(shù)據(jù)庫中添加新類或?qū)傩浴Ｗ詈?，在晶格結(jié)構(gòu)的轉(zhuǎn)化后，組織獲得的不同概化。

至于未來的工作，我們的目標是更多的細化我們的方法以及所有的步驟，并進一步研究前面提及的簡化方法。

參考文獻：

[1] Raschia G.Linguistic Summarization of a relation with Fuzzy Background Knowledge[M].BDA，2001.

[2] Saint Paul R， Raschia G， Mouadib N.Database Summarization： The SaintEtiQ System[J].ICD， 2007：1475-1476.

[3] Saint Paul R，Raschia G， Mouadib N.Résumé généraliste de bases de données [M].BDA，2005

[4] Dubois D， Prade H.Fuzzy sets in data summaries—outline of a new approach[C].Proceedings 8th Int. Conf. on Information Processing and Managament of Uncertainty in Knowledge-based，2000.

[5] Naoum L.Représentation de résumés de base de données par prototypes flous [M].14es Rencontres Francophones sur la Logique Floue et ses Applications （LFA），2006.

[6] Napoli A.Une introduction aux logiques de description[M].Technical Report， INRIA， 1997.

一旦數(shù)據(jù)庫模式和實例在邏輯描述中被指定，為了概化，一些規(guī)則就會被定義用來轉(zhuǎn)換數(shù)據(jù)庫。

4.2 數(shù)據(jù)庫轉(zhuǎn)換

如上所述，數(shù)據(jù)庫在描述邏輯語言時需要正式化，這樣其模式和實例就可以通過邏輯表達式來表示。因此，概化是一組新的邏輯表達式，其可以從原有的數(shù)據(jù)庫中導出。數(shù)據(jù)庫轉(zhuǎn)換包括很多方面：數(shù)據(jù)庫重組，屬性減少或分組以及實例的減少。事實上，我們可以為概化定義歸類，它表示一個層次關(guān)系，前類將被通用的類來代替，比如，圖1中類Circle將由類Shape代替。

關(guān)于屬性，需要考慮兩種可能性。第一，每個屬性都有一定的權(quán)重（由將來的數(shù)據(jù)庫用戶分配），表明有關(guān)的屬性是上下文相關(guān)的；第二，我們使用聚類算法，為具有一定接近度的屬性分組，在這種情況下，我們還可以定義一個與屬性權(quán)重相關(guān)的參數(shù)。

關(guān)于實例，我們使用符號數(shù)據(jù)技術(shù)來描述具有復雜和多值數(shù)據(jù)的元組。例如，對數(shù)值類型的屬性值進行概化，需要定義區(qū)間類型的符號對象，其邊界可以使用屬性的最小和最大值。在標稱類型屬性情況下，則需要生成一個符號對象，它是所有的屬性標稱值的集合。為了說明這一點，我們考慮下面的數(shù)據(jù)庫，其中包含類Circle的元組（表1）：

第一種概化方法是根據(jù)顏色的不同分，半徑值被替換為一個符號對象，它是一個區(qū)間，其中邊界表示半徑的最小值和最大值，如表2所示。

根據(jù)表3所示的半徑值，相同的元組可以有不同的概化。當然，我們也可以有其他結(jié)合，這取決于使用者的需求。

應(yīng)用上面介紹的轉(zhuǎn)換，一個數(shù)據(jù)庫可以產(chǎn)生不同的概化結(jié)果。下面，我們證明可以將所獲得的概化在晶格結(jié)構(gòu)中進行組織。

4.3 生成概化晶格

我們用S和使不同概化相互聯(lián)系的歸類Sub表示指生成的概化，把P（S）作為部分概化結(jié)果：P（S）={Si/Si[∈]S}，且S1，S2，S3三個概化均包含在S中，Sub有如下性質(zhì)：

反身性：?S1[∈]P（S） ： S1≤S1

對稱性： ?S1[∈]P（S） ， ?S2[∈]P（S） ： S1≤ S2 and S2≤S1? S1 = S2

傳遞性： ?S1， S2， S3[∈]P（S）3 ： S1≤S2 and S2≤S3 ?S1≤ S3

所以，Sub定義了一個偏序集，（P（S），Sub）定義了一個晶格。它有一個上界和下界，其中上界是初始的數(shù)據(jù)庫，下界是空集。

5 數(shù)據(jù)庫概化性能

我們大體上可以分為兩種標準：信息性和一致性。它們是成反比的，概化的越詳細，就越不一致。信息性測量了信息通過概化如何被給出，一致性了衡量了定義數(shù)據(jù)庫粒度所需的數(shù)據(jù)量。信息性與一致性的結(jié)合可以被視為選擇一個特定概化精度的標準。

6 結(jié)束語

在本文中，我們提出了基于描述邏輯的方法來建立數(shù)據(jù)庫概化晶格。我們的提議總共分三步：首先，使用描述邏輯（DL）語言正式化數(shù)據(jù)庫；其次，給原始數(shù)據(jù)庫的簡化定義規(guī)則，這些規(guī)則可用于減小模式，屬性和數(shù)據(jù)庫的實例。它并不是單一地簡化數(shù)據(jù)庫，它也可以在數(shù)據(jù)庫中添加新類或?qū)傩?。最后，在晶格結(jié)構(gòu)的轉(zhuǎn)化后，組織獲得的不同概化。

至于未來的工作，我們的目標是更多的細化我們的方法以及所有的步驟，并進一步研究前面提及的簡化方法。

參考文獻：

[1] Raschia G.Linguistic Summarization of a relation with Fuzzy Background Knowledge[M].BDA，2001.

[2] Saint Paul R， Raschia G， Mouadib N.Database Summarization： The SaintEtiQ System[J].ICD， 2007：1475-1476.

[3] Saint Paul R，Raschia G， Mouadib N.Résumé généraliste de bases de données [M].BDA，2005

[4] Dubois D， Prade H.Fuzzy sets in data summaries—outline of a new approach[C].Proceedings 8th Int. Conf. on Information Processing and Managament of Uncertainty in Knowledge-based，2000.

[5] Naoum L.Représentation de résumés de base de données par prototypes flous [M].14es Rencontres Francophones sur la Logique Floue et ses Applications （LFA），2006.

[6] Napoli A.Une introduction aux logiques de description[M].Technical Report， INRIA， 1997.

一旦數(shù)據(jù)庫模式和實例在邏輯描述中被指定，為了概化，一些規(guī)則就會被定義用來轉(zhuǎn)換數(shù)據(jù)庫。

4.2 數(shù)據(jù)庫轉(zhuǎn)換

如上所述，數(shù)據(jù)庫在描述邏輯語言時需要正式化，這樣其模式和實例就可以通過邏輯表達式來表示。因此，概化是一組新的邏輯表達式，其可以從原有的數(shù)據(jù)庫中導出。數(shù)據(jù)庫轉(zhuǎn)換包括很多方面：數(shù)據(jù)庫重組，屬性減少或分組以及實例的減少。事實上，我們可以為概化定義歸類，它表示一個層次關(guān)系，前類將被通用的類來代替，比如，圖1中類Circle將由類Shape代替。

關(guān)于屬性，需要考慮兩種可能性。第一，每個屬性都有一定的權(quán)重（由將來的數(shù)據(jù)庫用戶分配），表明有關(guān)的屬性是上下文相關(guān)的；第二，我們使用聚類算法，為具有一定接近度的屬性分組，在這種情況下，我們還可以定義一個與屬性權(quán)重相關(guān)的參數(shù)。

關(guān)于實例，我們使用符號數(shù)據(jù)技術(shù)來描述具有復雜和多值數(shù)據(jù)的元組。例如，對數(shù)值類型的屬性值進行概化，需要定義區(qū)間類型的符號對象，其邊界可以使用屬性的最小和最大值。在標稱類型屬性情況下，則需要生成一個符號對象，它是所有的屬性標稱值的集合。為了說明這一點，我們考慮下面的數(shù)據(jù)庫，其中包含類Circle的元組（表1）：

第一種概化方法是根據(jù)顏色的不同分，半徑值被替換為一個符號對象，它是一個區(qū)間，其中邊界表示半徑的最小值和最大值，如表2所示。

根據(jù)表3所示的半徑值，相同的元組可以有不同的概化。當然，我們也可以有其他結(jié)合，這取決于使用者的需求。

應(yīng)用上面介紹的轉(zhuǎn)換，一個數(shù)據(jù)庫可以產(chǎn)生不同的概化結(jié)果。下面，我們證明可以將所獲得的概化在晶格結(jié)構(gòu)中進行組織。

4.3 生成概化晶格

我們用S和使不同概化相互聯(lián)系的歸類Sub表示指生成的概化，把P（S）作為部分概化結(jié)果：P（S）={Si/Si[∈]S}，且S1，S2，S3三個概化均包含在S中，Sub有如下性質(zhì)：

反身性：?S1[∈]P（S） ： S1≤S1

對稱性： ?S1[∈]P（S） ， ?S2[∈]P（S） ： S1≤ S2 and S2≤S1? S1 = S2

傳遞性： ?S1， S2， S3[∈]P（S）3 ： S1≤S2 and S2≤S3 ?S1≤ S3

所以，Sub定義了一個偏序集，（P（S），Sub）定義了一個晶格。它有一個上界和下界，其中上界是初始的數(shù)據(jù)庫，下界是空集。

5 數(shù)據(jù)庫概化性能

我們大體上可以分為兩種標準：信息性和一致性。它們是成反比的，概化的越詳細，就越不一致。信息性測量了信息通過概化如何被給出，一致性了衡量了定義數(shù)據(jù)庫粒度所需的數(shù)據(jù)量。信息性與一致性的結(jié)合可以被視為選擇一個特定概化精度的標準。

6 結(jié)束語

在本文中，我們提出了基于描述邏輯的方法來建立數(shù)據(jù)庫概化晶格。我們的提議總共分三步：首先，使用描述邏輯（DL）語言正式化數(shù)據(jù)庫；其次，給原始數(shù)據(jù)庫的簡化定義規(guī)則，這些規(guī)則可用于減小模式，屬性和數(shù)據(jù)庫的實例。它并不是單一地簡化數(shù)據(jù)庫，它也可以在數(shù)據(jù)庫中添加新類或?qū)傩?。最后，在晶格結(jié)構(gòu)的轉(zhuǎn)化后，組織獲得的不同概化。

至于未來的工作，我們的目標是更多的細化我們的方法以及所有的步驟，并進一步研究前面提及的簡化方法。

參考文獻：

[1] Raschia G.Linguistic Summarization of a relation with Fuzzy Background Knowledge[M].BDA，2001.

[2] Saint Paul R， Raschia G， Mouadib N.Database Summarization： The SaintEtiQ System[J].ICD， 2007：1475-1476.

[3] Saint Paul R，Raschia G， Mouadib N.Résumé généraliste de bases de données [M].BDA，2005

[4] Dubois D， Prade H.Fuzzy sets in data summaries—outline of a new approach[C].Proceedings 8th Int. Conf. on Information Processing and Managament of Uncertainty in Knowledge-based，2000.

[5] Naoum L.Représentation de résumés de base de données par prototypes flous [M].14es Rencontres Francophones sur la Logique Floue et ses Applications （LFA），2006.

[6] Napoli A.Une introduction aux logiques de description[M].Technical Report， INRIA， 1997.