Operasi dan manipulasi data pada pada graf database menjadi hal menarik untuk dikaji seiring dengan berkembangnya penggunaan graf database. Salah satu contoh operasi dasar pada data graf yang paling sering digunakan adalah pencarian shortest path. Namun dengan semakin berkembangnya jumlah data, muncul permasalahan baru pada pencarian shortest path, yaitu dibutuhkan metode pencarian shortest path yang performansinya tidak terpengaruh pada jumlah data yang ada. Tree decomposition based indexing (TEDI) merupakan salah satu metode pencarian shortest path dengan menggunakan konsep indexing. Metode TEDI diawali dengan melakukan indexing. Proses indexing terdiri dari tiga tahap, yaitu reduksi graf, pembentukan tree dekomposisi, dan pencarian local shortest path yang menggunakan algoritma BFS. Setelah proses indexing, selanjutnya dilakukan pencarian shortest path secara bottom up memanfaatkan index yang sudah dibentuk. Dengan menggunakan metode ini, proses pencarian shortest path tidak terpengaruh pada ukuran graf, melainkan pada nilai derajat reduksi. Selain itu ukuran index yang dibentuk bisa disesuaikan berdasarkan nilai derajat reduksi. Olehkarena penelitian untuk mengetahui pengaruh ukuran graf terhadap performansi indexing dan pengaruh derajat reduksi terhadap performansi pencarian shortest path pada metode TEDI perlu dilakukan agar metode ini dapat diimplementasikan sesuai dengan keterbatasan sistem. Keterbatasan yang dimaksud adalah ketersediaan kapasitas media penyimpanan pada sistem untuk menyimpan index. Dari hasil penelitian diperoleh bahwa, untuk sistem memiliki keterbatasan media penyimpanan, maka ukuran index yang dihasilkan dapat diperkecil dengan meningkatkan nilai derajat reduksi, namun akibatnya performansi pencarian shortest path semakin menurun. Sebaliknya jika sistem memiliki kapasitas media penyimpanan yang cukup besar, maka performansi pencarian shortest path bisa ditingkatkan dengan memperkecil nilai derajat reduksi, namun akibatnya media penyimpanan yang digunakan untuk menyimpan index menjadi lebih besar.