Assuming a refactoring is needed (too big to be incorporated as part of an existing User Story) - is it okay to have a Refactoring 'story' on the Product Backlog?
The purpose of refactoring is not to change the behaviour of the system - so by definition no direct business value is given to the customer.
-- So does the Refactoring 'story' have story points which then count towards velocity or is this somehow cheating?
Context: We did an initial story storing some data in the simplest possible structure. The structure of this data is not going to work for an upcoming user story and requires a different approach, all existing functionality expecting the existing data structure will need to be changed to accommodate this new approach.
In my opinion it's absolutely fine to have this kind of item in your Product Backlog, since I've always taken the PB to be everything that needs to be done for the software to be complete.
I've routinely had features, bug-fixes, refactoring and research tasks in Product Backlogs before. If you don't put it in the backlog, how else would/could the task ever get done? You'll also want to have a definition of 'done' for the task, something that helps describes the aim of the refactoring (make code go faster, make code more test-able, etc.).