Kết quả của thí nghiệm được đưa ra trong Hình 3.4, trong đó chỉ có 2 trang trong mỗi tập trang khi hệ số chọn là 0.001. Nhưng khi hệ số chọn tăng lên thì kích thước đó cũng tăng lên theo; và chúng ta cũng nhận thấy rằng với việc hệ số chọn tăng thì các tập có số lượng các trang lớn sẽ được nhập lại thành tập lớn hơn. Và như vậy chúng ta sẽ thu được số tập trang ít hơn nhưng mỗi tập lại có số trang lớn hơn. Nguyên nhân của việc này là do xác suất để hai tập lớn nhập lại với nhau tăng lên rất nhanh khi hệ số chọn tăng. Hơn nữa khi hai tập trang này được hợp lại thì xác suất để các tập kết quả nhập lại với nhau lại càng lớn. Từ Hình 3.4 ta thấy rằng chỉ có 1 tập trang có có kích thước là 75 khi hệ số chọn là 0.01, và có 148 tập khác với kích thước nhỏ hơn 27. Khi hệ số chọn là 0.05 thì chỉ có hai tập trang với kích thước là 990 và 2.
Một ưu điểm của tập trang nhỏ là chúng ta chỉ cần lưu trữ những trang thuộc tập trang để thực hiện nối mà không cần phải truy cập lại trang. Với tập trang lớn hơn thì chúng ta có thể chia nhỏ chúng ra thành các tập nhỏ hơn bằng việc phân hoạch
đồ thị kết nối trang thành các đồ thị con.
Thay vì lưu trữ tất cả các trang của tập trang vào trong bộ nhớđệm, chúng ta có thể làm giảm kích thước bộ nhớ đệm bằng cách chỉ lưu trữ những bộ liên quan của các trang. Và bây giờ kích thước của bộ nhớ đệm sẽ phụ thuộc vào số các bộ cần thiết
phải lưu trữ. Lược đồ bộ nhớ đệm dựa trên việc lưu trữ trang hiện thời sẽđược thảo luận tiếp ở phần sau.
3.1.3 Xác định cận trên của kích thước bộ nhớđệm.
Chúng ta xem xét lược đồ truy xuất trang (page accessing scheme), trong đó trang dữ liệu chỉ được truy xuất nhiều nhất một lần. Việc này được thực hiện bằng cách
tìm về trang dữ liệu và lưu trữ các bộ liên quan của nó vào bộ nhớđệm cho đến khi những bộ tương ứng ở trong các trang khác được tìm vềsau đó. Độ lớn của bộ nhớ đệm chính cần thiết cho quá trình này là đáng kể. Kích thước này sẽ phụ thuộc vào trình tự truy cập trang dữ liệu. Trong phần này chúng ta sẽ tìm cách xác định cận trên của bộ nhớ đệm với đồ thị kết nối trang cho trước.Ý nghĩa của cận trên này là có ít nhất một dãy truy xuất trang cần đến lượng bộ nhớ đệm như vậy, nhưng cũng không có một trình tự truy xuất trang nào cần nhiều bộ nhớ hơn lượng này. Trước tiên chúng ta tổng quát hóa đồ thị kết nối trang bằng giả thiết rằng trang có thể chứa những bộ của nhiều hơn một quan hệ. Cạnh của đồ thị này được đánh trọng số, là số các bộ của một trang được nối với các bộ tương ứng trong trang khác. Chúng ta cũng tạm thời không xét đến các giá trị lặp trong các thuộc tính nối, và yếu tố lặp sẽ được xem xét sau. Hình 3.5 là một ví dụ vềđồ thị kết nối trang tổng quát, trong đó chỉ ra rằng trang 1 có n1 bộ và được nối với n1 bộ của trang 2. Ở phần tới các giải thuật để xác định bộ nhớ đệm cần thiết để thực hiện nối mà không cần phải truy xuất lại trang sẽđược giới thiệu.