Full Satisfiability of UML Class Diagrams (Extended Abstract)

Alessandro Artale, Diego Calvanese, and Angelica Ibanez-Garcia

Proc. of the 2009 Int. Workshop on Logic in Databases (LID 2009). Volume 127 of Computer Science Research Reports. 2009.

Class diagrams are one of the most important components of UML, the de-facto standard formalism for the analysis and design of software. The semantics of UML class diagrams is by now well established, and one can exploit automated reasoning tools that are based on the languages underlying their formalization to detect relevant properties, such as class satisfiability and subsumption. Among the reasoning tasks of interest, the basic one is detecting full satisfiability of a diagram, i.e., whether all classes and associations of the diagram can be simultaneously populated without violating any constraints of the diagram. While the complexity of class satisfiability has been studied extensively, full satisfiability received less attention. In this paper we address this problem, and establish tight upper and lower bounds for full satisfiability of UML class diagrams. Our results confirm the intuition that full satisfiability has the same computational complexity as class satisfiability.


@inproceedings{LID-2009,
   title = "Full Satisfiability of UML Class Diagrams (Extended Abstract)",
   year = "2009",
   author = "Alessandro Artale and Diego Calvanese and Angelica
Ibanez-Garcia",
   editor = "Leopoldo Bertossi and Henning Christiansen",
   booktitle = "Proc. of the 2009 Int. Workshop on Logic in Databases
(LID 2009)",
   pages = "15--26",
   volume = "127",
   publisher = "Roskilde University",
   series = "Computer Science Research Reports",
}
pdf