Testing

TECHNICAL REPORT 98-CSE-04

Semantic Caching and Query Processing

Qun Ren Margaret H. Dunham

Department of Computer Science and Engineering Southern Methodist University Dallas, TX 75275{0122 qren@seas.smu.edu May 26, 1998

Contents

1 Introduction 2 Related Research

2.1 Query Folding : : : : : : : : : : : : : 2.2 Caching Issues : : : : : : : : : : : : 2.2.1 Caching Granularity : : : : : 2.2.2 Caching Coherency Strategy 2.2.3 Caching Replacement Policy : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

1 2

2 3 4 5 5 6 9

3 Semantic Caching Model

3.1 Formal De nition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 3.2 The Semantic Cache Model : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : :

6

4 Semantic Caching Management

4.1 Query Admission : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 11 4.2 Coalescence and Decomposition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 12 4.3 Replacement Strategy : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 13

11

5 Query Processing

5.1 Formal De nition : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 14 5.2 Query Trimming : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 18 5.3 Query Processing : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : : 23

14

6 Conclusion

28

i

List of Figures

1 2 3 4 5 Possible Relations between Cache and Query Relations of Three Splitted Parts : : : : : : : D-LRU through an Example : : : : : : : : : : Possible Relations...