Moved the Store interface to a real key/value store

I can definitely remove that. I was wondering if we wanted to keep the original URI somewhere to make sure we don't loose any information.