Complexity of Reasoning over Temporal Data Models
MetadataShow full item record
We investigate the computational complexity of reasoning over temporal extensions of conceptual data models. The temporal conceptual models we analyse include the standard UML/EER constructs, such as isa between entities and relationships, disjointness and covering, cardinality constraints and their refinements, multiplicity and key constraints; in the temporal dimension, we have timestamping, evolution, transition and lifespan cardinality constraints. We give a nearly comprehensive picture of the impact of these constructs on the complexity of reasoning, which can range from NLogSpace to undecidability.