Record Details

Space optimization in deductive databases

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Space optimization in deductive databases
 
Creator SRIVASTAVA, DIVESH
SUDARSHAN, S
RAMAKRISHNAN, RAGHU
NAUGHTON, JEFFREY F
 
Subject database systems
logic programming
query languages
recursive functions
synchronization
 
Description In the bottom-up evaluation of logic programs and recursively defined views on databases, all generated facts are usually assumed to be stored until the end of the evaluation. Discarding facts during the evaluation, however, can considerably improve the efficiency of the evaluation: the space needed to evaluate the program, the I/O costs, the costs of maintaining and accessing indices, and the cost of eliminating duplicates may all be reduced. Given an evaluation method that is sound, complete, and does not repeat derivation steps, we consider how facts can be discarded during the evaluation without compromising these properties. We show that every such space optimization method has certain components, the first to ensure soundness and completeness, the second to avoid redundancy (i.e., repetition of derivations), and the third to reduce “fact lifetimes” (i.e., the time period for which each fact must be retained during evaluation). We present new techniques based on providing bounds on the number of derivations and uses of facts, and using monotonicity constraints for each of the first two components, and provide novel synchronization techniques for the third component of a space optimization method. We describe how techniques for each of the three components can be combined in practice to obtain a space optimization method for a program. Our results are also of importance in applications such as sequence querying, and in active databases where triggers are defined over multiple “events.”
 
Publisher Association for Computing Machinery
 
Date 2009-06-22T04:32:32Z
2011-12-08T08:13:13Z
2011-12-26T13:02:40Z
2011-12-27T05:49:18Z
2009-06-22T04:32:32Z
2011-12-08T08:13:13Z
2011-12-26T13:02:40Z
2011-12-27T05:49:18Z
1995
 
Type Article
 
Identifier ACM Transactions on Database Systems (TODS) 20(4), 472-516
0362-59154
10.1145/219035.219056
http://hdl.handle.net/10054/1554
http://dspace.library.iitb.ac.in/xmlui/handle/10054/1554
 
Language en