CHƯƠNG 4 THIẾT KẾ 4.1Các bước của giải thuật

Xem xét câu truy vấn “Where is the location of the Orange Bowl?”, từ quan hệ of nằm giữa hai thực thể là location và Orange Bowl. Đối với câu truy vấn “What state is the Filenes store located in?”, từ quan hệ in biểu diễn mối quan hệ LOCATEDIN giữa thực thể state và thực thể Filenes store nằm ở sau thực thể Filenes store. Trong câu “In what country is Angkor Wat?” từ quan hệ in nằm ở trước thực thể country dùng để biểu diễn mối quan hệ LOCATEDIN giữa thực thể country và thực thể Angkor Wat. Như vậy, từ quan hệ dùng để biểu diễn mối quan hệ giữa hai thực thể có thể nằm ở giữa, nằm ở sau hoặc nằm ở trước hai thực thể. Khi xem xét trên tập mẫu, từ quan hệ xuất hiện nhiều nhất là ở giữa hai thực thể. Do đó, để hình thành nên các bộ ba truy vấn , độ ưu tiên sẽ là vị trí của từ quan hệ đối với vị trí của hai thực thể. Ưu tiên thứ nhất là từ quan hệ nằm giữa hai thực thể, kế tiếp là từ quan hệ nằm sau hai thực thể và cuối cùng là từ quan hệ sẽ nằm phía trước hai thực thể. Các bộ ba này sau đó sẽ được so trùng với Ontology để xác định kiểu quan hệ tương ứng có trong Ontology.

Dựa vào các phân tích trên, đề tài đưa ra giải thuật xác định kiểu quan hệ giữa hai thực thể trong câu truy vấn như sau (Hình 4.2):

Hình 4.0.5: Xác định loại quan hệ giữa hai thực thể e_i và e_j.

• 
  Bước 1: Xét các từ quan hệ nằm giữa e_i và e_j. Bằng việc sử dụng tập luật, nếu có từ quan hệ nào khi kết hợp với e_i và e_j xác định được kiểu quan hệ giữa e_i và e_j thì quá trình dừng, ngược lại qua Bước 2.
  
• 
  Bước 2: Xét các từ quan hệ nằm ở sau e_i và e_j, tương tự như Bước 1, nếu không xác định được kiểu quan hệ giữa e_i và e_j thì qua Bước 3.
  
• 
  Bước 3: Xét các từ quan hệ nằm trước e_i và e_j.
  

Việc xác định kiểu quan hệ được làm bằng cách ứng với mỗi bộ ba ta sẽ ánh xạ thành . Việc ánh xạ này được thực hiện qua giải pháp lập từ điển (Tập luật) và heuristic. Quá trình ánh xạ được khái quát bằng lược đồ như ở Hình 4.3.

Chi tiết cho lược đồ tại Hình 4.3 được diễn dịch như sau:

• 
  Xét mối quan hệ có dạng [C₁, S₁] – RW – [C₂, S₂] với:
  
  • 
    RW là từ quan hệ,
    
  • 
    C₁ và C₂ lần lượt là lớp của thực thể thứ nhất và thứ hai,
    
  • 
    S₁ và S₂ lần lượt là giá trị chuỗi ban đầu của thực thể thứ nhất và thứ hai.
    
• 
  Ta sẽ lần lượt xây dựng các ánh xạ sau đây:
  
  • 
    Ánh xạ từ quan hệ RW thành quan hệ R₁ - tập những quan hệ có thể tương ứng với từ quan hệ RW. Ví dụ từ quan hệ “’s” tương ứng với tập các quan hệ {HASWIFE, HASSON, HASCAPITAL, …}
    
  • 
    Ánh xạ từ quan hệ (C₁, C₂) thành quan hệ R₂ - tập những quan hệ có thể có giữa C₁ và C₂. Ví dụ giữa hai lớp (PERSON, PERSON) ta có tập các quan hệ sau: {HASWIFE, HASFATHER, HASMOTHER, …}
    
  • 
    Ánh xạ (S₁, RW) thành R₃ - tập những quan hệ có thể có nếu biết từ quan hệ RW và giá trị chuỗi ban đầu S₁. Ví dụ với (wife, ’s) sẽ được ánh xạ thành tập quan hệ {HASWIFE}.
    
  • 
    Ánh xạ (RW, S₂) thành R₄ - tập những quan hệ có thể có nếu biết từ quan hệ RW và giá trị chuỗi ban đầu S₂. Ví dụ với (has, mother) sẽ được ánh xạ thành tập quan hệ {HASMOTHER}
    
• 
  Ta có thể dễ dàng nhận thấy R₃, R₄ đều là tập con của R₂. Gọi R là mối quan hệ thật sự của từ quan hệ RW. Chắc chắn R  R₁  R₂. Ngoài ra, trong một số trường hợp, có thể R  R₁  R₃ hoặc R  R₁  R₄ hoặc R sẽ thuộc giao của cả bốn tập hợp trên. Như vậy, về lý thuyết ta có thể xác định được quan hệ R nếu xây dựng đầy đủ cả bốn tập hợp trên.
  
• 
  Việc xây dựng tập ánh xạ R₃ và R₄ được thực hiện bằng hệ thống luật. Chi tiết về hệ thống luật sẽ được trình bày ở phần sau.
  

4.1.10Xoá bỏ quan hệ không phù hợp

Sau Bước 4.1.9 (Xác định loại quan hệ giữa các thực thể), có một số quan hệ được xác định nhưng không phù hợp với ngữ cảnh của câu truy vấn, các loại quan hệ này sẽ được xóa bỏ. Bước này sử dụng các heuristic sau để xóa bỏ các quan hệ không phù hợp:

• 
  Nếu hai thực thể E_i và E_i+1 cách nhau bởi dấu phẩy, thì E_i+1 chỉ quan hệ với E_i, các mối quan hệ của E_i+1 với các thực thể khác sẽ bị xóa bỏ. Ví dụ trong câu “What's the population of Biloxi, Mississippi?”, tồn tại các quan hệ:
  

[CITY:Biloxi](POPULATIONCOUNT)[STRING:?]
[PROVINCE:Mississippi](POPULATIONCOUNT)[STRING:?]
[CITY:Biloxi](SUBREGIONOF)[PROVINCE:Mississippi]

Hai thực thể Biloxi và Mississippi cách nhau bởi dấu phẩy, do đó quan hệ thứ hai được xóa bỏ.

• 
  Nếu E_i và E_i+1 đứng liền kề nhau, hoặc cách nhau bằng từ quan hệ “’s”, thì các quan hệ của E_i với các thực thể trước nó sẽ bị xóa bỏ. Ví dụ, trong câu “What is the name of Neil Armstrong’s wife?” có các quan hệ:
  

[PERSON:Neil Armstrong]( HASLABEL)[LABEL:?]
[PERSON:*](HASLABEL)[LABEL:?]
[PERSON:Neil Armstrong](HASWIFE)[PERSON:*]

Vì thực thể wife có quan hệ với thực thể Neil Armstrong bằng từ quan hệ ‘s. Do đó quan hệ đầu tiên được xóa bỏ.

• 
  Trong trường hợp một thực thể có quan hệ với nhiều thực thể đứng trước nó, thì chỉ giữ lại mối quan hệ với thực thể không xác định đứng trước, gần nó nhất. Ví dụ, trong câu truy vấn “What city in Florida is Sea World in?” có ba loại quan hệ:
  

[COMPANY:Sea World](LOCATEDIN)[CITY:?]
[CITY:?](LOCATEDIN)[PROVINCE:Florida]
[COMPANY:Sea Word](LOCATEDIN)[PROVINCE:Florida]

Quan hệ thứ hai bị xóa bỏ.

4.1.11Xác định quan hệ giữa tính từ và thực thể

Tại bước này, ta sẽ xét các liên kết giữa tính từ và thực thể, được gọi là một bộ hai .

Xem xét câu truy vấn “What famous model was married to Billy Joel?”, tính từ famous nằm trước thực thể model. Đối với câu truy vấn “Name a tiger that is extinct?”, tính từ extinct nằm sau thực thể tiger. Như vậy, tính từ liên kết với một thực thể có thể nằm trước, hoặc nằm sau thực thể đó. Khi xem xét trên tập mẫu, tính từ xuất hiện nhiều nhất là ở trước thực thể. Do đó, để hình thành nên các bộ hai truy vấn , độ ưu tiên sẽ được quyết định dựa vào vị trí của tính từ đối với vị trí của thực thể. Ưu tiên nhất là tính từ nằm trước thực thể, cuối cùng là tính từ nằm sau thực thể. Các bộ hai sau đó sẽ được so trùng với Ontology để xác định kiểu quan hệ tương ứng có trong Ontology.

Dựa vào các phân tích trên, đề tài đưa ra giải thuật xác định kiểu quan hệ giữa tính từ và thực thể trong câu truy vấn như sau (Hình 4.4):



Hình 4.0.7: Xác định loại quan hệ giữa tính từ adj và thực thể.

• 
  Bước 1: Xét các thực thể nằm sau tính từ adj. Bằng việc sử dụng tập luật, nếu có thực thể e_j nào khi kết hợp với adj mà xác định được kiểu quan hệ giữa adj và e_j thì quá trình dừng, ngược lại qua Bước 2.
  
• 
  Bước 2: Xét các thực thể e_i nằm ở trước adj.
  

Bằng giải thuật trên, chúng ta xác định được kiểu quan hệ giữa tính từ adj và e nếu giữa chúng có mối quan hệ với nhau trong ngữ cảnh của câu truy vấn. Quá trình được áp dụng tương tự cho tất cả các cặp tính từ, thực thể trong câu truy vấn. Các kiểu quan hệ tìm được sẽ được thêm vào danh sách quan hệ RELATION.

Việc xác định kiểu quan hệ được làm bằng cách ứng với mỗi bộ hai ta sẽ ánh xạ thành . Việc ánh xạ này cũng được thực hiện bằng giải pháp lập từ điển (Tập luật) và heuristic, tương tự quá trình ánh xạ bộ ba thành đã được trình bày tại Bước 4.1.9. Quá trình ánh xạ được khái quát bằng lược đồ Hình 4.5.

Hình 4.0.8: Lược đồ ánh xạ kiểu quan hệ giữa tính từ và thực thể.

Chi tiết cho lược đồ tại Hình 4.5 được diễn dịch như sau:

• 
  Xét mối quan hệ có dạng: [ADJ] – [E, S] với:
  
  • 
    ADJ là tính từ,
    
  • 
    E là lớp của thực thể liên kết với tính từ được xem xét.
    
  • 
    S là giá trị chuỗi ban đầu của thực thể E.
    
• 
  Ta sẽ lần lượt xây dựng các ánh xạ sau đây:
  
  • 
    Ánh xạ tính từ ADJ thành tập R₁ các bộ ba quan hệ . Ví dụ, tính từ famous tương ứng với tập các bộ ba quan hệ {, , ,}
    
  • 
    Ánh xạ (ADJ, E) thành tập R₂ các bộ ba quan hệ có thể biểu diễn tính từ ADJ đối với thực thể E. Ví dụ, giữa tính từ famous và lớp PERSON, ta có thể có các bộ ba sau: {, }
    
  • 
    Ánh xạ (ADJ, S) thành R₃ - tập các bộ ba có thể có nếu biết tính từ ADJ và giá trị chuỗi ban đầu S. Ví dụ, (famous, model) sẽ được ánh xạ thành tập quan hệ {}
    
• 
  Ta có thể dễ dàng nhận thấy R₂, R₃ đều là tập con của R₁. Gọi R là mối quan hệ thật sự biểu diễn bộ hai . Chắc chắn R  R₁  R₂  R₃. Như vậy, về lý thuyết ta có thể xác định được quan hệ R nếu xây dựng đầy đủ cả ba tập hợp trên.
  
• 
  Việc xây dựng tập ánh xạ R₁, R₂ và R₃ được thực hiện bằng hệ thống luật. Chúng ta sẽ đi vào chi tiết về hệ thống luật này ở phần sau.
  

4.1.12Xây dựng đồ thị ý niệm

Sau khi đã xác định được tất cả các quan hệ có trong câu truy vấn, bước này sẽ xây dựng đồ thị ý niệm mô tả câu truy vấn. Như ta đã phân tích ở trên, để mở rộng giải quyết cho những truy vấn hỏi về số lượng, truy vấn có tính từ, tính từ so sánh nhất, liên từ luận lý yêu cầu phải mở rộng CG. Phương pháp tiếp cận đã kế thừa và đồng thời hiệu chỉnh lại Bước 12 (Xây dựng đồ thị ý niệm) trong kết quả nghiên cứu của tác giả [18] để biểu diễn được những thành phần mới bổ sung của đồ thị ý niệm mở rộng. Chúng ta sẽ đi vào chi tiết về cách lưu trữ và hiển thị đồ thị ý niệm ở phần tiếp theo sau.

Каталог: nonghocbucket -> UploadDocument server07 id114188 190495
UploadDocument server07 id114188 190495 -> ChuyêN ĐỀ ĐIỀu khiển tán sắC
UploadDocument server07 id114188 190495 -> Trong khuôn khổ Hội nghị của fifa năm 1928 được tổ chức tại Amsterdam (Hà Lan), Henry Delaunay đã đưa ra một đề xuất mang tính đột phá đối với lịch sử bóng đá
UploadDocument server07 id114188 190495 -> MỤc lục phần I: MỞ ĐẦU
UploadDocument server07 id114188 190495 -> «Quản trị Tài sản cố định trong Công ty cổ phần Điện lực Khánh Hòa»
UploadDocument server07 id114188 190495 -> Khóa luận tốt nghiệp 2010 Mục tiêu phát triển kinh tế xã hội trong thời kì tới 85
UploadDocument server07 id114188 190495 -> ĐỒ Án tốt nghiệp tk nhà MÁY ĐƯỜng hiệN ĐẠi rs
UploadDocument server07 id114188 190495 -> Đề tài: Qúa trình hình thành và phát triển an sinh xã hội ở Việt Nam
UploadDocument server07 id114188 190495 -> Chuyên đề tốt nghiệp Trần Thị Ngọc – lt2 khct L ời cảM ƠN
UploadDocument server07 id114188 190495 -> Địa vị của nhà vua trong nhà nước phong kiến Việt Nam

tải về 0.6 Mb.

Chia sẻ với bạn bè của bạn: