POTENTIAL SELECTION CASES IN DTDS

In the real world, a web user usually tries to find the information relevant to a given topic. The categorization of web databases into subject (topic) domains can help to alleviate the time-consuming problem of searching a large number of databases. Once the user submits a query, he/she is directly guided to the appropriate web databases with relevant topic documents. As a result, the database selection task will be simplified and become effective.

In this section, we will analyze potential database selection cases in DTDs, based on the relationships between the subject domains that the content of the databases may cover. If all the databases have the same subject domain as that which the user query involves, relevant documents are likely to be found from these databases. Clearly, under such a DTD environment, the above database selection task will be drastically simplified. Unfortunately, the databases distributed on the Internet, especially those large-scale commercial web sites, usually contain the documents of various topic categories. Informally, we know that there exist four basic relationships with respect to topic categories of the databases: (a) identical; (b) inclusion; (c) overlap; and (d) disjoint .

The formal definitions of different potential selection cases are shown as follows :

Definition 6

For a given user query q , if the contents of the documents of all the databases come from the same subject domain(s), we will say that an identical selection case occurs in DTDs corresponding to the query q .

 

Definition 7

For a given user query q , if the set of subject domains that one database contains is a subset of the set of subject domains of another database, we will say that an inclusion selection case occurs in DTDs corresponding to the query q .

 

For example, for database S _i , the contents of all its documents are only related to the subject domains, c ₁ and c ₂ . For database S _j , the contents of all its documents are related to the subject domains, c ₁ , c ₂ and c ₃ . So, C _i ‚ C _j .

Definition 8

For a given user query q , if the intersection of the set of subject domains for any two databases is empty, we will say that a disjoint selection case occurs in DTDs corresponding to the query q . That is, ˆ S _i , S _j ˆˆ S ( 1 ‰ i, j ‰ n, i ‰  j ), C _i ˆ C _j = ˜.

 

For example, suppose database S _i contains the documents of subject domains c ₁ and c ₂ , but database S _j contains the documents of subject domains c ₄ , c ₅ and c ₆ . So, C _i ˆ C _j = ˜.

Definition 9

For a given user query q , if the set of subject domains for database S _i satisfies the following conditions: ˆ S _j ˆˆ S ( 1 ‰ j ‰ n, i ‰  j ), (1) C _i ˆ C _j ‰  ˜, (2) C _i ‰  C _j , and (3) C _i C _j or C _j C _i , we will say that an overlap selection case occurs in DTDs corresponding to the query q .

 

For example, suppose database S _i contains the documents of subject domains c ₁ and c ₂ , but database S _j contains the documents of subject domains c ₂ , c ₅ and c ₆ . So, C _i ˆ C _j = c ₂ .

Definition 10

For a given user query q , ˆ S _i , S _j ˆˆ S ( 1 ‰ i, j ‰ n, i ‰  j ), c _k ˆˆ C _i ˆ C _j ( 1 ‰ k ‰ p ) and the subsets of documents corresponding to topic category c _k in these two databases, D _ik and D _jk , respectively. If they satisfy the following conditions:

1. the numbers of documents in both D _ik and D _jk are equal, and

2. all these documents are the same,

then we define D _ik = D _jk . Otherwise, D _ik ‰  D _jk .

 

Definition 11

For a given user query q , ˆ S _i , S _j ˆˆ S ( 1 ‰ i, j ‰ n, i ‰  j ), if the proposition c _k ˆˆ C _i ˆ C _j ( 1 ‰ k ‰ p ), D _ik = D _jk ’ Simi _Li (D _ik , q) = Simi _Lj (D _jk , q) is true, we will say that a non - conflict selection case occurs in DTDs corresponding to the query q . Otherwise, the selection is a conflict selection case . Simi _Li (S _i , q) (1 ‰ i ‰ n ) is the local similarity function for the i th database with respect to the query q .

 

Theorem 1

A disjoint selection case is neither a non-conflict selection case nor a conflict selection case.

 

Proof: For a disjoint selection case, ˆ S _i , S _j ˆˆ S ( 1 ‰ i, j ‰ n, i ‰  j ), C _i ˆ C _j = ˜, and D _i ‰  D _j . Hence, databases S _i and S _j are incomparable with respect to the user query q . So, this is neither a non-conflict selection case nor a conflict selection case.

By using a similar analysis to those on the previously page, we can prove that there are seven kinds of potential selection cases in DTDs as follows:

1. Non-conflict identical selection cases

2. Conflict identical selection cases

3. Non-conflict inclusion selection cases

4. Conflict inclusion selection cases

5. Non-conflict overlap selection cases

6. Conflict overlap selection cases

7. Disjoint selection cases

In summary, given a number of databases S , we can first identify which kind of selection case exists in a DTD based on the relationships of subject domains among them.