Digital media has created more opportunities for stories to be interactive, allowing the user to participate in plot events and even change the direction of a story. Interactivity can make stories more engaging however if the plot can change as a result of user input then the story becomes non-linear. The resulting system is known as a potential narrative because a narrative is only presented through user interaction. Non-linear stories require extra considerations and content compared to a linear story of similar length. Computer generated content for video games has grown as a field and this raises the possibility of using computer assistance for the creation and management of interactive stories. This thesis explores the paradigm required for both computers and developers to understand potential narratives. The success of a potential narrative requires the same coherency and credibility that a regular story does, in addition to a new layer known as player agency. Coherency refers to the logical causal progression of a plot, credibility is the verisimilitude of the presented story world and player agency is how satisfying the interactive elements are. These three criteria are the guiding principles for the creation of an intuitive potential narrative model. We present a state transition model for potential narratives as well as a prototype using relational programming to generate coherent traversals through a manually authored potential narrative. / Thesis / Master of Applied Science (MASc) / Writing stories for video games and interactive fiction is a time consuming and complex affair. The resulting web of possible events and pathways through the non-linear story is known as a potential narrative. Computer assisted tools for creating potential narratives could cut down on production costs and open the door for stories that are able to adapt to the player in real-time. In order for these generated stories to be viable they must be coherent, credible and allow for player agency. These criteria describe whether stories make logical sense and are satisfying for the user to interact with. Taking that into account we present a model for coherent interactive stories which keeps track of the story world and the events that could happen within it. As a proof of concept we implement this model with a prototype to generate traversals through a manually authored potential narrative.