Database Complexity Metrics CoraI Calero, Mario Piattini, Marcela Genero GmpO ALARCOS - Departamentode Inform;itica Universidad de Castilla-LaMancha- SPAIN email: {ccalero, mpiattin meenero l @inf-ct.uclm.es choosing between different design alternatives or Abstract giving designers limit values for certain Metrics are useful mechanisms for improving characteristics (analogously to value 10 for Mc the quality of soji`vvareproducts and also for Cabe complexity of prograrns). Some recent determim.ngthe best ways ro help practitioners and proposals have been published for conceptual researchers. UnfortunateLy,almost all the metrics schemata ([20], [24], [28]) but for conventional put forward focus on program characteristz`cs databases,such as relationalones, nothing has been disregardz.ng databases. However, databases are proposed, excepting normalizationtheory. becomz`ng more compLex, and it is necessary to Databasesare becoming more complex, and it is measure schemata complexity in order to understand, necessaryto measureschematacomplexityin orderto monz.tor, control, predict and z.mprove database understand,monitor, control, predict and improve development and ma"zntenanceprojects. In fizz's databasedevelopment and maintenance projects.In paper, we will present dierent measures in order to modem Information Systems (IS), the databasehas measure the complexz-ty that aJTects the become a crucial component, so there is a need to maintainabz"Iz.ty of the relational, object-relatz`onal propose and study some measures to assess its and active database schemas. However it is not quality. enough to propose the metrics, a formaL validatz.on Database quality depends on several factors: is also needed for know!ng thez.r mathematz.caL functionality, reliability, usability, efficiency, characteristics. We wz.II present the two main maintainability and portability ([15]). Our focus is tendencz.es in metrics formal validation, axz`omatz.c on maintainability because maintenance accounts approaches and measurement theory" However, for 60 to 90 percent of life cycle costs and it is research !nto sofiware measurement is needed considered the most importantconcern for modem from a theoretz`caLbut also jrom a practical point of IS departments([1l], [22], [29]). view ((121). For thz`sreason, we wz`LL also present The International Standard, ISO/IEC 9126, some of the experzments that we have developedfor distinguishes five subcharacteristics for the dijferent ia`ndsof databases. maintainability: analysability, changeability, stability, testability and compliance. Analysability, changeability and testability are in turn influenced 1.IntroducBon by complexity ([191). However, a general complexity measure is "the impossibLe holy grail" Software engineers have been proposing large ([9]), i.e" it is impossible to get one value that quantities of metrics for software products, captures all the complexity factors of a database processes and resources ([l0], [23], [37]). Metrics ,Henderson-Sellers([14]) dis6nguishes three types are useful mechanisms for improving the quality of of complexity: computational, psychological and software products and also for determiningthe best representational, nd for psychological complexity ways to help practitioners and researchers ([26]). he considers three components: problem Unfortunately, almost all the metrics put forward complexity, human cognitive factors and product focus on program characteristics (e"g" McCabe complexity. The last one is our focus and for our ([21]) cyclomatic number) disregarding databases purposes the productwill be databases. ([34]). As far as databases are concerned, metrics Our goal is to propose internal measures for have been used for comparing data models rather databases, which can characterisetheir complexity than the schemata itself. Several authors ([2], [16], helping to assess database maintainability (the [17], [18], [32], [33]) have comparedthe most well external quality characteristic). In the next section known models such as NIAM and relational we will present the framework followed to define using different metrics. Although we think this and validate databasemetrics. work is interesting,metrics for comparingschemata Section three summarizes the proposed metrics are needed mostly for practical purposes, like for relational, object-relational and active QuaTIC'2OOI/ 79 databases. In section four the formal validation of (such as [37] or [36]) specify a general some of these metrics is described. Some empirical framework in which measures should be validations are presented in section five and defined. Measurement theory gives clear conclusions and future work will be presented in definitions of terminology, a sound basis sections six and seven respectively. of software measures, criteria for experimentation,conditions for validation 2. A Framework for Developing and of software measures, foundations of Validating Database Metrics. prediction models, empirical properties of software measures, and criteria for As we have said previously, our goal is to measurementscales. define metrics for controlling database Empirical vaBdaOon. The goal of this maintainability. However, metrics definition must step is to prove the practical utility of the be done in a methodological way, so it is necessary proposed metrics~ Although there are to follow a numberof steps co ensure the reliability various ways of performing this step, of the proposed metrics. Figure 2 presents the basically we can divide the empirical method we apply for the metrics proposal. validation into experimentation and case studies. Experimentation is usually made using controlled experiments and the case METRIC studies usually work with real data. Both ~ ~,~ .--. ~ . . of them are necessary, the controlled experiments as a first approach and the case studies for backing up the results . In this section, we present the different metrics that we have proposed for relational. object relational and active databases. For each kind of database, a brief summary of its main Figure 2. Steps followed in the definition and characteristics is given and an example using validation of the databasemetrics ANSI/ISO SQL:1999 code is used to illustrate the calculation of the proposed metrics. In this figure we have three main activities: Metrics for Rela6onul Databases Metrics definition The first step is the Traditionally, the only indicator used to proposal of metrics. Although it looks measure the "quality" of relational databases has simple, it is an importantone in ensuring been the normalization theory, with which [13] metrics are correctly defined. This propose to obtain a normalization ratio. However, definition is made taking into account the we think that normalization is not enough to specific characteristicsof the databasewe measure complexity in relational databases, so we want to measure and the experience of propose the following four metrics in addition to normalization ([5]): database designers and administratorsof these databases. TheoreBeal validation. The second step is Number of aun.buzes (NA) NA is the number of attributes in all the tables the formal validation of the metrics. The of the schema. formal validation helps us to know when and how to apply the metrics. There are Depth Referential Tree (DRT) two main tendencies in metrics validation: DRT is defined as the lenoothof the longest the frameworks based on axiomatic referentialpath in the database schema. Cycles are approaches and the ones based on the only consideredonce. measurementtheory. The goal of the first ones is merely definitional. The most well- known frameworks of this type are those proposed by [351, [3] and [251. The measurement theory-based frameworks 80 / QuaTIC2001 Number of Foreign Keys (NFK) In this schema the value of the metrics are: NA The NFK metric is defined as the number of = 12, DRT = 1, NPK = 2, COS =9. foreign keys in the schema. Cohesion of the schema (COS) Metrics for Object-Relotional Databases COS is defined as the sum of the square of the An object-relational database schema is number of tables in each unrelated subgraph of the composed of a number of tables related by database schemata that is: referential integrity, which have columns that can |USj 2 |US| numberof unrelatedsubgraphs be defined over simple or complex (user-defined) COS - .S JV7USi - NTUSi number of tables in the data types. We define the next metrics for object- z=1 ` related subgraph"i" relational databases ([4J): We apply the previous metrics to the following example (suppliers-and-parts Schema Si~e (SS) database) taken from [61: We define the size of a system as the sum of the size of every table (TS) in the schema: CREATE TAELE S ( S# S#, SNAME NAME, STATUS STATUS, CITY CITY, PRIMARY KEY (S#)); The table size (TS) measures the size not only CREATE TABLE P in terms of the simple columns (defined using ( P# P# simple domains) bot also in terms of complex PNAME NAME, columns (defined using user-defined classes). COLOR COLOR, Formally it can be defined as the sum of the total WEIGHT WEIGHT, size of the simple columns (TSSC) and the total CITY CITY, size of the complex columns (TSCC) in the table. PRIMARY KEY (P#)); TSSC is simply the number of simple columns in CREATE TABLE SP the table (considering that each simple domain has ( S# S#, a size equal to one). TSCC is defined as the sum of P# P#, complex columns size (CCS). The size of a QTY QTY, complex column is no more than the size of the PRIMARY KEY (S#, P#), class hierarchy above the columnand is defined as FOREIGN KEY (S#) weighted by the number of complex columns which NCES S, use the hierarchy. Finally, the size of a class FOREIGN KEY (P#) hierarchy is defined as the sum of the size of each REFERENCES P); class on the hierarchy. For more details about the precise definition of this metric see [4J. This relational database schema can be representedas Complexz"tyof references between tables (DRT, a relationalgraph (see figure 3). NFK) In object-relational databases, other characteristicsof relational databases are preserved. Metrics related with the referential integrity, such S as NI:;Kand DRT proposed in the previous section, can also be used. SP We can apply these metrics to the following P example: CREATE TYPE projectAS ( name CHAR(10), Fiooure3. Relational graphfor the example budget FLOAT); QuaTIC'2001/ 81 CREATE TYf E employee AS ( which has a link (either directly or emp_num INTEGER, transitively) with at least one cause of Si. level INTEGER, D, the distance. This measure correspondsto salary_base FLOAT, the length of the longest path that connects proj project) Si with any of its anchors. method calc_salary() RETURNS DECIMAL(72)); TP, the triggering potential. Given a triggeringgraph < S, L >, and a node of the graph, rule Si, the number of causes of Si, is the sum of weights of the incoming arcs arriving at Si. The triggeringpotential for a rule R is the quotient between the number of Name data SHOT SADT DTS potential causes of Si, and Sis event type SAS + CAS cardinality~ ROJECT 0 2+O 2 EMPLOYE I 3+2 6 CREATETRIGGERONE AFTERDELETE ON TABLE3 FOREACH ROW WHEN (OLD.NUMBER=3) BEGIN DELETEFROM TABLE4 WHERE TABLE4.S#=:TABLE3"J#; END ONE; CREATETRIGGERTWO Let us assume that all methods have a AFTERDELETE ON TABLE4 cyclomatic complexity equal to 1. In table 1, we FOREACH ROW WHEN COLD.NAME=.SMITH) present the value of the size of each datatype. BEGIN Table 1. Size values of the datatypes DELETEFROMTABLE5 WHERE TABLE4.S#=:OLD.S#: END TWO; Then, the values for the other metrics are: SHC = 6, CCS = 3, TSCC = 6, TSSC - 2, TS = 8, SS - For trigger ONE, NA = I, TP = I and D = I, for 8. trigger TWO, NA = 1, TP = 1, and D = 2. Mebies for Active Databases 4. Metrics Formaf VaRdation When measuring active databases,we can make use of the notion of a triggering graph as defined in There are two main tendencies in metrics [I]. A triggering graph is a pair where S validation: the frameworks based on axiomatic represents the set of ECA rules, and L is a set of approachesand the ones based on the measurement directedarcs where an arc is drawnfrom Si to Sj if theory. The goal of the first ones is merely Sis action causes the happening of an event definitional~On this kind of formal framework, a occurrence that participates in Sjs events. This set of formal properties is defined for a given notion of triggering graph is modified by [71 in two software attribute and it is possible to use this aspects. Firstly, arcs are weighted by the numberof propertyset for classifying the proposed measures. potential event occurrences produced by the The most well-known frameworks of this type triggering rule Ci.e. Si) that could affect the rule are those proposed by [351, [3], and [25]. The main triggered off (i.e. Sjs event). Secondly, the nodes goal of axiomatisationin software metrics research S are extended with the set of transactions T. A is the clarification of concepts to ensure that new transaction is an atomic set of (database) actions metrics are in some sense valid. The measurement where any of these actions could correspondto an theorybased frameworks (such as [37} or {36]) event triggering one or more rules. Therefore, T specify a general framework in which measures nodes will have outgoing links but never incoming should be defined, Measurement theory gives clear links, as we assume that a transactioncan never be definitions of terminology, a sound basis of triggered from within a rules action or another software measures, criteria for experimentation, transaction. conditions for validation of software measures, The active databasecould be characterisedby the foundations of prediction models, empirical following triggeringgraphmeasures([8]): properties of software measures, and criteria for . NA the minimum number of anchors measurementscales. The discussion of scale types required to encompass the whole set of is importantfor statistical operations. potential causes of Si. An anchor is a In this section, we will present the results of the transaction node of the triggering graph, formal verification of the presented metrics with 82 J QuaTIC'2OOI results of an experimentation depend on careful, rigorous and complete experimental design. A claim that a measure is valid because it is a good predictor of some interesting attribute can be justified only by formulatinga hypothesis about the relationshipand then testing the hypothesis ([10]). BRIANO ET ZUSE(1998) AL(1996) In the rest of this section, we summarize R different experimentsthat we have done with some E NFK COMPLEXHY ABOVE THE ORDINA of the metrics discussed in this chapter.All of these L initial experimentsrequire further experimentation V E DRT LENGT ABOVE THE ORDINAL in order to validate the findings. However, these results can be useful as a starting point for future N research. A NA SLZ ABOVE THE ORDINA A complete description of the experiments can L be found in [5] for relational database metrics, in COS 512 RATIO [27] for object-relationalones and in [8] for active ones. SS SIZ ABOVE THE ORDINA Relational experiment Our objective was to demonstrate that the TS SIZE ABOVE THE ORDINA metrics related with referential integrity (DRT and ) can be used for measuring the complexity of the relational database schema, which influences in NA COMPLEXITY ABOVE THE ORDINA the relational database understandability. The participants of this study were computer science TP NOT ABOVE THE ORDINA students at the University of Castilla-La Mancha CLASSIPIAB (Spain), who were enrolled in a two-semester D LENGT ABOVE THE ORDINA databases course. Based on the results of this experiment, we concluded that the number of foreign keys in a relational database schema is a more solid indicator of its understandability than | Table 4. Summary of metrics formal validation the length of the referential tree. This metric is not relevant by itself, but can modulate the effect of the With the axiomatic approach results we can number of foreign keys in a database system know, for example for relational databases that we need some metrics for capturing cohesion and Object-relational experiment coupling and covering all the characteristics Five object-relational databases were used in defined by the framework From the measurement this experiment with an average of 10 relations per theory results we can know what kind of database. Five subjects participated in the operations it is possible to make with the defined experiment. All of them were experienced in both metrics, the statistics that it is possible to apply to relational databases and object-oriented them etc. programming. To analyze the usefulness of the metrics, we used two techniques: C4.5 ([30]), a machine learning algorithms, and RoC ([31]), a 5. Metrics Empirical VaBdaHon robust Bayesian classifier. In conclusion, both the In the past, empirical validation bas been an techniques discover that the table size is a good informal process relying on the credibility of the indicator for the understandability of a table. The proposer. Often , when a measure was identified depth of the referential tree is also presented as an theoretically as an effective measure of complexity, indicator by C4.5 but not clearly by RoC. The practitioners and researchers began to use the number of foreign keys does not seem to have a metric without questioning its validity. Today, real impact on the understandability of a table. many researchers and practitioners assume that validation of a measure (from a theoretical point of Active experiment view) is not sufficient for widespread acceptance. Our objective was to assess the influence of D They expect the empirical validation to demonstrate and TP in rule interaction understandability. that the measure itself can be validated. Useful However, such understanding could be influenced QuaTIC'2001/ 83 by how the reasoning is conducted. As rules can be presented some of the experiments that we have seen as cause-and-effect links, two questions can be developed for the different kinds of databases. posed by the user: "what effects can a rule produce Nevertheless controlled experimentshave problems (forward reasoning)?" or "how can an effect be (like the large number of variables that causes produced (backwardreasoning)?".The participants differences) and limits (they do not scale up, are of the experimentwere final-year computerscience done in a class in training situations, are made in students at the University of the Basque Country, vitro and face a variety of threats of validity). who were enrolled in an advance database course Thereforeit is convenient to run multiple studies, The students were already familiar with relational mixing controlled experimentsand case studies. For database, and some laboratories were previously these reasons, a more in depth empirical evaluation conducted on the definition of triggers. For the is under way in collaboration with industrial and forward experiment, we concluded that the public organizationsin "rear situations. triggering potential in a databaseschema is a solid indicator of its understandability, and that the ACKNOWLEDGEMENT distance is not relevant by itself and cannot This research is part of the MANTICA project, modulate the effect of the triggeringpotential. For partially supported by the CICYT and the European the backward experiment we concluded that both Union (CICYT-1FD97-0168) and by the CALIDAT metrics are solid indicatorsof its understandability. project carried out by Cronos Iberica (supported by All the experiments described need to be the Consejeria de Educaci6n de la Comunidad de replicated in orderto obtain more consistent results. Madrid, Nr, 09/0013/1999) However, controlled experiments made in a laboratoryare useful as a startingpoint but present some problemssuch a the large numberof variables REFERENCES that can cause differences- Therefore, it is convenient to also run case studies working with 1- Aiken, A., Hellerstein, J.M. and Widow, J. real data. (1995). Static analysis techniques for predicting the behaviour of active database 6. Conclusions and Future Work rules. ACM Transactionson Databases, 20 (1), 341. Databases are becoming more complex, and it is ?.. Batra, D., Hoffer, J.A. and Bostrom, R.P. necessary to measureschemata complexity in order (1990). A comparison of user performance to understand, monitor, control, predict and between the relational and the extended entity improve database development and maintenance relationshipmodels in the discovery phase of projects. Database metrics could help designers, databasedesign. CACM, 33 (2), 126 139. choosing between alternative semantically 3. Briand, L.C., Morasca, S. And Basin, V. equivalent schemata, to select the most (1996). Property-based software engineering maintainable one and understandtheir contribution measurement. IEEE Transactions on Software to the overall IS maintainability. Engineering,Vol.22(1). pp~68-85. We have put forward different measures (for 4. Calero, C`, Piattini, M, Ruiz, F~ and Polo, M. internal attributes) in order to measure the (1999) Validation of metrics for Object" complexity that affects the maintainability (an Relational Databases, International Workshop external attribute)of the relational, object-relational on QuantitativeApproaches in Object-Oriented and active databaseschemas. Software Engineering (ECOOP99), Lisbon However it is not enough to propose the (Portugal), 14-18 June metrics, a formal validation is also needed for 5. Calero, C., Piattini, M , Genero, M., Serrano, knowing their mathematical characteristics. We M. and Caballero, I. (2000). Metrics for have presented the two main tendencies in metrics Relational Databases Maintainability, formal validation, axiomatic approaches and .CKAI52000, Cardiff,UK. measurement theory. Although the information 6. Date., C.J. (1995). An Introductionto Database obtainedfrom both techniques is different,the final Systems. 6th. Addison-Wesley, Reading, objective is the same, to obtain objective Massachusetts- mathematical information of the metrics we are 7. Diaz, 0. and Piattini, M (1999). Metrics for working on. active databases maintainability. CAISE99. However, as we have indicated previously, Heidelberg,June 1618. research into software measurement is needed 8. Dfaz. O., Piattini. M y Calero, C. (2001). also from a practical point of view. We have Measuring active databases maintainability. 84 1 QuaTIC2001 Accepted for publication in Information 24. Moody, D~ L. (1998). Metrics for Evaluating Systems Journal the Quality of Entity Relationship Models. 9. Fenton, N. (1994). Software Measurement:A Proc. of the Seventeenth International Necessary Scientific Basis. IFRE Transactions Conference on Conceptual Mode|ling (ER'98), on Software Engineering,20(3), 199-206. Singapore. 1O. Fenton, N, andPfJeeger S. L. ( / 997). Software 25. Morasca, S, and Briand,I .C. (1997). Towards Metrics: A Rigorous Approach 2nd. edition. a Theoretical Framework for measuring London, Chapman& Hall. software attributes.Proceeding of the Fourth ll" Frazer, A. (1992)~ Reverse engineering-hype, International,Software Metrics Symposium, hope or here?. In; P.A.V. Hall, Software Reuse 119-126. and Reverse Engineering in Practice. Chapman 26. Pf|eager, S. L. (1997). Assessing Software & Hall. Measurement. IEEE Software. March/April, 12. Glass, R. (1996). The Relationship Between 25-26. Theory and Practice in Software Engineering. 27. Piattini, M., Calero, C., Sahraoui, H. and Software, November, Vol.39 (11). pp 11- Loams, H. (2000) An empirical Study with object-relational database metrics, 13, Gray R.ff.M., Carey B.N., McGlynn N.A., ECOOP:2OOO, Cannes, I3 June. Pengelly A.D., (1991), Design metrics for 28. Piattini, M., Genera, M,, Calero, C., Polo, M. databasesystems. BT Technology J, Vol 9, 4 and Ruiz, F. (2001). Metrics for Managing Oct. pp. 69-79 Quality in InfOrrnation Mode|ling. In: 14. Henderson-Sellers, B- (1996). Object-Oriented "Information Modeling in the New Mefrics - Measures of CompJexity. Prentice- MiJJennium"M. Rossi and K. Siau (eds.), Idea Hall, Upper Saddle River, New Jersey. Group Publishing,USA. 15. ISO, (1994). Software Product Evaluation 29. Pigoski, T.M. (1997). Practical Software Quality Characteristicsand Guidelines for their Maintenance. Wiley Computer Publishing. Use. ISO/IECStandard9126, Geneva. New York, USA. 16. Jarvenpaa, S. and Machesky, J~ (1986). End 30. Quinlan, J.R.. C4.5: Programs for Machine user learning behaviorin data analysis and data Learning, (1993), Morgan Kaufmann modeling tools. Proc. of the 7th Int. Conf. on Publishers. InformationSystems, San Diego, 152-167. 31. Barnaul, M. and Sebastiani, P. Bayesian 17. Juhn, S. and Naumann, J. (1985). The methods for intelligent data analysis. In M effectiveness of data representation Berthold and D.J. Hand, editors, An characteristicson user validation. Proc. of the Introductionto Intelligent Data Analysis, (New 6th Int. Conf. on Information Systems, York, 1999). Springer. Indianapolis,212-226. 32. Rossi, M. and Brinkkemper, S. (1996). 18. Kim, Y.G. and March, S.T. (1995). Complexity Metrics for Systems Development Comparing Data Modeling Forrnalisms~ Methods and Techniques. InformationSystems CACM 38(6), /03-1 15. 21(2), 209-227. 19. Li, HF. and Cheng, W.K. (1987). An empirical 33. Shoval, P. and Even-Chaime, M (1987). study of software metrics. IEEE Trans. on Database schema design: An experimental SoftwareEngineering, 13 (6), 679-708~ comparison between normalization and 20. MacDonell, S.G., Shepperd, MJ. and Sallis, informationanalysis. Database 18(3), 3039. P"J.(1997). Metrics for Database Systems; An 34" Sneed, H.M and Foshag. O. (1998). Measuring Empirical Study. Proc. Fourth International Legacy Database Structures. Proc of The Software Metrics Symposium - Metrics'97, European Software Measurement Conference Albuquerque.IEEE ComputerSociety, 99-107. FESMA 98, Antwerp, May 6-8, Coombes, Van 21. McCabe, T.J. (1976). A complexity measure. Huysduynen and Peelers (eds.), 199-211. IEEE Trans. Software Engineering 2(5), 308- 35. Weyuker, E.J. (1988). Evaluating software 320. complexity measures. IFFE Transactions on 22. McClure, C. (1992) The Three Rs of Software Software Engineering Vol.14(9). pp. 1357- Automation: Reengineering, Repository, 1365. Reusability.Englewood Cliffs: Prentice-Hall. 36. Whitmire, S.A. (1997), Object OrientedDesign Melton, A. (ed.) (1996). Software Measurement,Ed. Wiley. Measurement.London, International Thomson 37. 2use, H. (1998). A Framework of Software ComputerPress. Measurement.Berlin, Walter de Gruyter QuaTIC 2001 / 85