Anzeige
Erschienen in:
2010 | OriginalPaper | Buchkapitel
Full Satisfiability of UML Class Diagrams
verfasst von : Alessandro Artale, Diego Calvanese, Angélica Ibáñez-García
Erschienen in: Conceptual Modeling – ER 2010
Verlag: Springer Berlin Heidelberg
Aktivieren Sie unsere intelligente Suche, um passende Fachinhalte oder Patente zu finden.
Wählen Sie Textabschnitte aus um mit Künstlicher Intelligenz passenden Patente zu finden. powered by
Markieren Sie Textabschnitte, um KI-gestützt weitere passende Inhalte zu finden. powered by
UML class diagrams (UCDs) are the de-facto standard formalism for the analysis and design of information systems. By adopting formal language techniques to capture constraints expressed by UCDs one can exploit automated reasoning tools to detect relevant properties, such as schema and class satisfiability and subsumption between classes. Among the reasoning tasks of interest, the basic one is detecting
full satisfiability
of a diagram, i.e., whether there exists an instantiation of the diagram where
all
classes and associations of the diagram are non-empty and all the constraints of the diagram are respected. In this paper we establish tight complexity results for full satisfiability for various fragments of UML class diagrams. This investigation shows that the full satisfiability problem is E
xp
T
ime
-complete in the full scenario, NP-complete if we drop
isa
between relationships, and NL
og
S
pace
-complete if we further drop covering over classes.