Hi,
My question as follows:
In theoretical computer science, there is a concept of complexity classes for example NP-Completeness. I want to know the research or any views to relate NP-completeness with the UML 2.0?
regards,
I’m a Postdoctoral Researcher at SOM Research Team, in Barcelona. Currently, I’m involved in the development of scalable tools for MDE, especially in the persistence of Very Large Models.
UML is a very expressive notation and thus algorithms having to manipulate UML models suffer from complexity problems.
For instance, reasoning on UML class diagrams is EXPTIME-complete and, when general OCL constraints are allowed, it becomes undecidable
Interesting question. To the best of my knowledge, no one has studied it. I wonder whether the question has been asked of any other language, including ones such as C.
The complexity of UML is often cited as one of its primary drawbacks. In arguing this, many people will point to the apparent simplicity of programming languages such as Java. However, while Java is relatively simple on its own, you have to consider how much of the necessary complexity has been swept under the rug of class libraries? As far as I can tell, you cannot write anything remotely useful in Java unless you are also proficient with at least some of the core Java libraries. In environments such as J2EE or Eclipse, the minimum level of proficiency goes up even further — exceeding in complexity anything that UML requires.
Consequently, although I do think that UML is bloated needlessly, I think it is mere pittance compared to what you find in the so-called “mainstream” languages used for most applications development.
The problem is that we are trying to solve complex problems. As any carpenter can tell you, complex problems require complex tools. You can program almost anything you like with something as elementary as a Turing machine, but most people would prefer to use something a little more sophisticated. So, an unconditional argument against complexity in a computer language is a bit unfair. The trick is to find the right degree of complexity — and this is generally a discretionary call.
To avoid confusion, complexity classes as NP etc. are used to model complexity of problem/algorithms on Turing machines. These classes are independent of programming or modeling language, e.g. a problem, which is in NP, will be NP no matter what language you use.
If you want to compare languages, you can look on the complexity of description of problems in those langauges. This is called Kolmogorov’s complexity. It IS a good measure TO compare efficiency OF descriptions – e.g. compression algorithms, but it IS NOT good FOR comparing efficiency OF programming/modeling languages. AFAIK, there isn’t a good measure for that.
There are correspondences btw complexity classes and relational languages. Their most famous one is perhaps ESO = NP by Fagin 1974, stating that expressiveness of existential second order logic corresponds to NP. Since then, many correspondences have been found.
(-> Finite Model theory)
Concerning UML it seems that even a simple inheritance between classifiers already needs a second order language to be expressed*. Thus the expressiveness/ complexity of UML should reach NP and above quite easily.
Regards
|=
*sth like IF generalCls R someCls THEN specialCls R someCls, where R (the relation) is a Variable and thus requires second order language.
For most people, UML is a graphic notation. And this notation is used as a medium to explain and descript software architecture and concepts.
In this sence, UML does not need so much complexity because typically when describing an architecture you dont really care about detail like visibility of variable, code inside method and all.
You just describe a high view behaviour. It is for humans. Not computers.
Then some people were thinking that we could do more with UML. Instead of just using it for documentation or describing things, they wanted the description to be good enough to create the software.
This is what introduced so much complexity with UML2, MDA and all.
Problem is, textual representation is more efficiant. Outside of some specific tasks where the graphical representation is in direct relation with the intended result (UI design…), programs are better described by text than graphics.
With text, you have freedom. With a few key strokes you can import any module/class, call any method you need. You can write the code you want. You can switch between dozen of files in no time and see the exact behaviour of your software by reading the code. You can debug, you can see what happens. You can use SCM, versionning and merge. It just works, it’s effective.
This IS NOT possible WITH graphical tools FOR now. I think that everybody realised that.
So people try TO use UML FOR code generation OF boiler plate code, LIKE database access. Because FOR a single class, you generate maybe ten files. THEN the fact you need MORE TIME TO CREATE a class USING UML than code IS relativised by the fact one UML class would generate 3,5, 10 class AND a few configuration files.
It works, but… It give you nearly nothing. If you can generate FROM an UML diagram, you can generate too FROM a text file… AND you have everything a text file can AND an UML diagram can’t.
Last, if it so repetitive maybe you don’t want TO generate AT ALL. LIKE we don’t care about the bytecode generated from our javacode, we might don’t care about the generated code FROM the configuration file. Just use a DSL that DESCRIBE what you needs IN a very concise way. AND this DSL will likely come IN an text representation.
So yes Java, J2EE IS MORE complex than UML. But it needs this complexity AND it manage it better than UML. Because AT anytime, WITH code you have FULL power AND you do everything everywhere IN an effiscient maner.
In reply to Nicolas:
The big difference between modeling languages like UML and programming languages like Java, is that in case of modeling languages, there is a PRIMARY requirement that the artifacts generated with it must be understandable to human readers. In contrast, the primary requirement of programming languages is that they can be understood by computers. The tension between these two has been present since the very beginning of computing and, so far, the latter approach has been dominant — to our detriment I am afraid, since many of the problems with software can be traced to the sheer impenetrability of lines-upon-lines of cryptic program code. In the late 1950’s an attempt was made TO move a BIT IN the opposite direction, AND we introduced so-called high-LEVEL languages. AT the TIME, there was much skepticism that these things would ever be practical, AND there was a major outcry by programmers that they were losing “full power”. IN retrospect, we know that these folks were wrong AND that the little control that was lost was NOT comparable TO the lot that was gained IN productivity AND quality. (Nicolas’ argument about “full power” and the ability to do “everything everywhere” reminds me somewhat of this.)
With the increase in computing power (with many thanks to the hardware people, whose contribution to their successes software people tend to neglect), we can being to depart even further from our current computer-centric language rut, which has mostly produced slightly better derivatives of Fortran (a line of Java is scarcely more productive than a line of Fortran). This is what so-called model-based software development is about: a movement to the next generation of languages (finally!).
Regarding the question of textual versus graphical syntax, I do not see it as an either-or issue. There are certain things much better expressed using graphical representations while others are expressed better using text. For example, a graphical representation of a hierarchical statechart, with elements such as group transitions and history, can capture very, very complex complex behaviour in an extremely concise yet very intuitive way. Doing the same with textual equivalent would be not only more tedious and more error prone, but also pretty much incomprehensible(I speak from 15 years of experience of applying statecharts in industrial software). On the other hand, specifying a complex mathematical expression using graphics would in most cases be less concise and less understandable than a textual representation.
In my experience, combining the two syntactical forms works best. I see no reason why we should be bound to the tyranny of a single form. There have been many successful large industrial projects where this approach was used — most of them actually based on a combination of UML graphical syntax for higher-level aspects of a software system (e.g., high-level component structures and high-level behaviours) and a textual syntax, using a standard textual language such as C++ or Java, for the detailed algorithmic stuff. (For this purpose the OMG recently adopted the ALF language to complement UML; it is primarily intended for specifying fine-grained behavior, using a strictly textual syntax, but which is embedded in a higher-level UML model.)
I am talking here about projects that use fully automated complete-system code generation from such models and not the code skeletons that Nicolas’ seems TO have experience WITH. Here ARE a couple OF convenient REFERENCES OF a NUMBER OF non-trivial industrial projects OF this TYPE:
[1] T. Weigert AND F. Weil. Practical experience IN USING model-driven engineering TO develop trustworthy computing systems. IN Proceedings OF the IEEE International Conference ON Sensor Networks, Ubiquitous, AND Trustworthy Computing, volume 1 OF 57, pages 208217, 2006.
[2] N. J. Nunes, B. Selic, A. R. da Silva, AND J. A. T. Álvarez, editors. UML Modeling Languages AND Applications, UML 2004 Satellite Activities, Lisbon, Portugal, October 11-15, 2004, Revised Selected Papers, volume 3297 OF Lecture Notes IN Computer Science. Springer, 2005
The folks working ON these projects have discovered the productivity, quality, AND maintenance advantage OF USING modeling languages such AS UML directly FOR implementation. So, IN fact, we CAN do MORE WITH UML; it’s not just a fantasy. In fact, we have been doing this successfully for at least 20 years now. I have no doubt that much of these benefits experienced in these projects can be traced directly to the human-centered (as opposed to computer-centered) nature of the languages used.
So, while text has its advantages — e.g., we have some very powerful tools for handling text — I cannot accept a claim that we should do all of our programming using purely textual languages. The computer is such a wonderfully flexible device that it would be a shame to limit it to textual input only. And, long-standing experience has shown that it need not be so.
Cheers…Bran
I am not sure this is exactly on topic for the original post, but I believe that the UML abstract syntax can actually be defined using first order logic* through metamodeling. I haven’t had TIME TO fully WORK this out, but if you ARE interested, you can take a look AT http://lib.modeldriven.org/MDLibrary/trunk/Pub/Papers/Model%20Semantics%20and%20Mathematical%20Logic.pdf.
As TO UML semantics, I believe UML IS basically AS expressive AS FIRST-order logic. AT least, the semantics OF the fUML executable subset IS basically grounded IN FIRST order logic IN its spec (http://www.omg.org/spec/FUML/CURRENT).
— Ed
*Note: I noticed I left out the key phrase “using first order logic” when I posted this originally!
Hi,
This is one of the paper related to calculate NP completeness for UML Class diagram by intoducing an algorithm. The algorithm computes the conistencies of class diagrams with respect to size to P, NP, PSPACE or EXPTIME. Details can be found here.
On the Complexities of Consistency Checking for Restricted
UML Class Diagrams
http://www2.nict.go.jp/x/x163/kaneiwa/uml-ex.pdf
FOR example, IN the CASE OF a state machine the correspondence TO complexity classes IS rather obvious. There one can immediately see that, if its model employs a History Element H the implementation LANGUAGE requires a correspondingly higher expressiveness. Thus one can take this INTO consideration, WHEN e.g. choosing a suitable Issue tracking tool FOR implementing the state flow.
In the CASE OF class diagrams one employment OF inheritance implies a certain minimal LEVEL OF complexity*, thus one could immediately see, since this LEVEL cannot be checked by running tests ON the application alone, one has TO carry out code reviews IN order TO verify the application comprehensively.
Thus, I believe that applying complexity classes TO UML can provide a substantial benefit, if it can support the controlled (complexity aware) use OF LANGUAGE, i.e. if one decides the application TO cover a higher complexity, one IS immediately aware OF the higher implementation cost. Finally, complexity awareness IS cost awareness.
Also here: http://BIT.ly/ga6BbV