Title :
String-oriented databases
Author :
Rajasekar, Arcot
Author_Institution :
Supercomput. Center, California Univ., San Diego, La Jolla, CA, USA
Abstract :
Relational databases and Datalog view each attribute as indivisible. This view, though useful in several applications, does not provide a suitable database paradigm for use in genetic, multimedia or scientific databases. Data in these applications are unstructured; querying on sub-strings of attribute values is often necessary. Moreover due to imprecision and incompleteness in the data, approximate reasoning also becomes indispensable. Our aim is to view strings as database objects that can be compared, divided, subsumed, interpreted and approximated. Allowing such operations on strings enriches the semantics and increases the expressive power of database languages. We develop an extension to the relational algebra, augmenting it with the concept of a string expression with a rich structure of string variables, mapping functions, interpreted string operations and approximate evaluations. We study properties of such expressions and show that many of the well-known properties of relational algebra hold in the extension. We also discuss an extension to Datalog(String) and an implementation of a prototype system called S-log. S-log integrates pattern matching in Datalog framework. We contend that string oriented database systems would be useful in applications that require efficient sub-structure analysis, such as aligning DNA strings using motifs, retrieving and synthesizing iconic images based on content
Keywords :
DATALOG; query processing; relational algebra; relational databases; string matching; DNA strings; Datalog; S-log; approximate evaluations; approximate reasoning; attribute values; database languages; database objects; database paradigm; expressive power; iconic images; interpreted string operations; mapping functions; pattern matching; relational algebra; relational databases; string expression; string oriented database systems; string oriented databases; string variables; sub-structure analysis; Algebra; DNA; Database languages; Database systems; Genetics; Image analysis; Multimedia databases; Pattern matching; Prototypes; Relational databases;
Conference_Titel :
String Processing and Information Retrieval Symposium, 1999 and International Workshop on Groupware
Conference_Location :
Cancun
Print_ISBN :
0-7695-0268-7
DOI :
10.1109/SPIRE.1999.796591