Expressing and optimizing sequence queries in database systems
| Autor: | Carlo Zaniolo, Amir M. Zarkesh, Jafar Adibi, Reza Sadri |
|---|---|
| Rok vydání: | 2004 |
| Předmět: |
SQL
Sequence Theoretical computer science Exploit Database Computer science InformationSystems_DATABASEMANAGEMENT Full text search Extension (predicate logic) Query optimization computer.software_genre Query language Spatial query Data mining computer Information Systems computer.programming_language |
| Zdroj: | ACM Transactions on Database Systems. 29:282-318 |
| ISSN: | 1557-4644 0362-5915 |
| DOI: | 10.1145/1005566.1005568 |
| Popis: | The need to search for complex and recurring patterns in database sequences is shared by many applications. In this paper, we investigate the design and optimization of a query language capable of expressing and supporting efficiently the search for complex sequential patterns in database systems. Thus, we first introduce SQL-TS, an extension of SQL to express these patterns, and then we study how to optimize the queries for this language. We take the optimal text search algorithm of Knuth, Morris and Pratt, and generalize it to handle complex queries on sequences. Our algorithm exploits the interdependencies between the elements of a pattern to minimize repeated passes over the same data. Experimental results on typical sequence queries, such as double bottom queries, confirm that substantial speedups are achieved by our new optimization techniques. |
| Databáze: | OpenAIRE |
| Externí odkaz: |
|