SpiderLink: a Keyword Search Algorithm
Author
Butenas, Linas
Term
10. Term
Education
Publication year
2003
Abstract
Mange brugere vil gerne kunne søge i relationsdatabaser ved at skrive nøgleord, ligesom på nettet, uden at skrive SQL-forespørgsler. For at muliggøre dette har vi udviklet SpiderLink, en nøgleordsbaseret søgemaskine til relationsdatabaser. SpiderLink bruger en k-tree (k-træ) datastruktur til at finde, hvordan nøgleord, der findes i forskellige tabeller og rækker, hænger sammen. Den returnerer sekvenser af rækker (tupler), der viser de forbindelsesveje, som knytter rækkerne med nøgleordene sammen. I afhandlingen definerer vi k-tree og forklarer dets vigtigste egenskaber: det håndterer hierarkiske, parallelle og simple relationer i en database; det er minimal (gemmer kun nødvendige forbindelser); det er afgrænset for en given database; og det kan implementeres som en hashtabel for hurtige opslag. Derefter præsenterer vi SpiderLink-algoritmen og viser i et trin-for-trin-diagram, hvordan den virker i praksis. SpiderLink er fuldt implementeret, og tests på databaser bekræfter vores teoretiske antagelser.
Many users want to search relational databases by typing keywords, like on the web, without writing SQL queries. To enable this, we developed SpiderLink, a keyword search engine for relational databases. SpiderLink uses a k-tree data structure to discover how keywords found in different tables and rows are connected. It returns sequences of rows (tuples) that show the paths linking the rows where the keywords occur. In the thesis, we define the k-tree and explain its key properties: it handles hierarchical, parallel, and simple relationships in a database; it is minimal (stores only the necessary links); it is finite for a given database; and it can be implemented as a hash table for fast lookups. We then present the SpiderLink algorithm and illustrate it with a step-by-step diagram showing how it works. SpiderLink is fully implemented, and tests on databases support our theoretical assumptions.
[This abstract was generated with the help of AI]
Documents