Reachability Problems in Entity-Relationship Schema Instances

Recent developments in reification of ER schemata include automatic generation of web-based database administration systems [1,2]. These systems enforce the schema cardinality constraints, but, beyond unsatisfiable schemata, this feature may create unreachable instances. We prove sound and complete characterisations of schemata whose instances satisfy suitable reachability properties; these theorems translate into linear algorithms that can be used to prevent the administrator from reifying schemata with unreachable instances.