Title :
Efficient Rewriting Algorithms for Preference Queries
Author :
Georgiadis, Periklis ; Kapantaidakis, Ioannis ; Christophides, Vassilis ; Nguer, Elhadji ; Spyratos, Nicolas
Author_Institution :
Dept. of Comput. Sci., Univ. of Crete, Heraklion
Abstract :
Preference queries are crucial for various applications (e.g. digital libraries) as they allow users to discover and order data of interest in a personalized way. In this paper, we define preferences as preorders over relational attributes and their respective domains. Then, we rely on appropriate linearizations to provide a natural semantics for the block sequence answering a preference query. Moreover, we introduce two novel rewriting algorithms (called LBA and TBA) which exploit the semantics of preference expressions for constructing progressively each block of the answer. We demonstrate experimentally the scalability and performance gains of our algorithms (up to 3 orders of magnitude) for variable database and result sizes, as well as for preference expressions of variable size and structure. To the best of our knowledge, LBA and TBA are the first algorithms for evaluating efficiently arbitrary preference queries over voluminous databases.
Keywords :
query processing; rewriting systems; block sequence answering; natural semantics; preference queries; rewriting algorithms; Database systems; Explosions; Helium; Inspection; Modems; Performance gain; Scalability; Software libraries;
Conference_Titel :
Data Engineering, 2008. ICDE 2008. IEEE 24th International Conference on
Conference_Location :
Cancun
Print_ISBN :
978-1-4244-1836-7
Electronic_ISBN :
978-1-4244-1837-4
DOI :
10.1109/ICDE.2008.4497519