Abstract

Metrics are useful mechanisms for improving the quality of soji`vvareproducts and also for determim.ngthe best ways ro help practitioners and researchers. UnfortunateLy,almost all the metrics put forward focus on program characteristz`cs disregardz.ng databases. However, databases are becomz`ngmore compLex,and it is necessary to measure schemata complexityin order to understand, monz.tor, control, predict and z.mprove database development and ma"zntenanceprojects. In fizz's paper, we will present dierent measures in order to measure the complexz-ty that aJTects the maintainabz"Iz.toyf the relational, object-relatz`onal and active database schemas. However it is not enough to propose the metrics, a formaL validatz.on is also needed for know!ng thez.r mathematz.caL characteristics. We wz.II present the two main tendencz.es in metrics formal validation, axz`omatz.c approaches and measurement theory" However, research !nto sofiware measurement is needed from a theoretz`caLbut also jrom a practical point of view ((121). For thz`sreason, we wz`LaLlso present some of the experzments that we have developedfor the dijferent ia`ndsof databases.

-

Software engineers have been proposing large quantities of metrics for software products, processes and resources ([l0], [23], [ 37 ]). Metrics are useful mechanisms for improvingthe quality of softwareproducts and also for determiningthe best ways to help practitioners and researchers ([ 26 ]). Unfortunately, almost all the metrics put forward focus on program characteristics (e"g" McCabe ([ 21 ]) cyclomatic number) disregardingdatabases ([ 34 ]). As far as databasesare concerned, metrics have been used for comparing data models rather than the schemata itself. Several authors ([2], [ 16 ], [ 17 ], [ 18 ], [ 32 ], [ 33 ]) have comparedthe most well known models such as NIAM and relational using different metrics. Although we think this work is interesting,metrics for comparingschemata are needed mostly for practical purposes, like choosing between different design alternatives or giving designers limit values for certain characteristics (analogously to value 10 for Mc Cabe complexity of prograrns). Some recent proposals have been published for conceptual schemata ([ 20 ], [ 24 ], [ 28 ]) but for conventional databases,such as relationalones, nothing has been proposed, excepting normalizationtheory.

Databasesare becoming more complex, and it is necessaryto measureschematacomplexityin orderto understand,monitor, control, predict and improve databasedevelopment and maintenanceprojects.In modem InformationSystems (IS), the databasehas become a crucial component, so there is a need to propose and study some measures to assess its quality.

Database quality depends on several factors: functionality, reliability, usability, efficiency, maintainabilityand portability ([ 15 ]). Our focus is on maintainability because maintenance accounts for 60 to 90 percent of life cycle costs and it is considered the most importantconcern for modem IS departments([1l], [ 22 ], [ 29 ]).

The International Standard, ISO/IEC 9126, distinguishes five subcharacteristics for maintainability: analysability, changeability, stability, testability and compliance. Analysability, changeability and testability are in turn influenced by complexity ([191). However, a general complexity measure is "the impossibLe holy grail" ([ 9 ]), i.e" it is impossible to get one value that captures all the complexity factors of a database ,Henderson-Sellers([ 14 ]) dis6nguishes three types of complexity: computational, psychological and representational, nd for psychological complexity he considers three components: problem complexity, human cognitive factors and product complexity. The last one is our focus and for our purposesthe productwill be databases.

Our goal is to propose internal measures for databases,which can characterisetheir complexity helping to assess database maintainability (the external quality characteristic). In the next section we will present the framework followed to define and validate databasemetrics.

Section three summarizes the proposed metrics for relational, object-relational and active databases.In section four the formal validation of some of these metrics is described.Some empirical validations are presented in section five and conclusions and future work will be presentedin sections six and seven respectively.

2. A Framework for Developing Validating Database Metrics. and

As we have said previously, our goal is to define metrics for controlling database maintainability. However, metrics definition must be done in a methodological way, so it is necessary to follow a numberof steps co ensurethe reliability of the proposed metrics. Figure 2 presents the method we apply for the metricsproposal.

~ ~,~M.-E-.TR~.I C. Metrics definition The first step is the proposal of metrics. Although it looks simple, it is an importantone in ensuring metrics are correctly defined. This definition is made taking into account the specific characteristicsof the databasewe want to measure and the experience of database designers and administratorsof these databases.

TheoreBeal validation. The second step is the formal validation of the metrics. The formal validation helps us to know when and how to apply the metrics. There are two main tendencies in metrics validation: the frameworks based on axiomatic approaches and the ones based on the measurementtheory. The goal of the first ones is merely definitional.The most wellknown frameworks of this type are those proposed by [351, [ 3 ] and [251. The measurement theory-based frameworks (such as [ 37 ] or [ 36 ]) specify a general framework in which measures should be defined. Measurement theory gives clear definitions of terminology, a sound basis of software measures, criteria for experimentation,conditions for validation of software measures, foundations of prediction models, empirical properties of software measures, and criteria for measurementscales.

Empirical vaBdaOon. The goal of this step is to prove the practical utility of the proposed metrics~ Although there are various ways of performing this step, basically we can divide the empirical validation into experimentation and case studies. Experimentationis usually made using controlled experimentsand the case 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 differentmetrics that we have proposed for relational. object relational and active databases. For each kind of database, a brief summary of its main characteristics is given and an example using ANSI/ISO SQL:1999 code is used to illustratethe calculationof the proposedmetrics.

Metrics for Rela6onul Databases

Traditionally, the only indicator used to measure the "quality" of relational databases has been the normalization theory, with which [13] propose to obtain a normalization ratio. However, we think that normalization is not enough to measure complexity in relational databases, so we propose the following four metrics in addition to normalization ([ 5 ]):

Number ofaun.buzes (NA)

NA is the number of attributesin all the tables of the schema.

Depth Referential Tree (DRT)

DRT is defined as the lenoothof the longest referentialpath in the database schema. Cycles are only consideredonce.

CREATE TAELE S

( S# S#,

SNAME NAME,

STATUS STATUS,

CITY CITY,

PRIMARY KEY (S#));

CREATE TABLE P

( P# P#

PNAME NAME,

COLOR COLOR,

WEIGHT WEIGHT,

CITY CITY,

PRIMARY KEY (P#));

CREATE TABLE SP

( S# S#, P# P#, QTY QTY,

PRIMARY KEY (S#, P#),

FOREIGN KEY

NCES S,

FOREIGN KEY

REFERENCES P);

SP S P (S#) (P#)

Number of Foreign Keys (NFK)

The NFK metric is defined as the number of foreign keys in the schema.

Cohesion ofthe schema (COS)

COS is defined as the sum of the square of the number of tables in each unrelated subgraph of the database schemata that is:

|USj 2 |US| numberof unrelatedsubgraphs COS - .S JV7USi - NTUSi number of tables in the z=1 ` related subgraph"i"

We apply the previous metrics to the following example (suppliers-and-parts database) taken from [61:

In this schema the value of the metrics are: NA

= 12, DRT = 1, NPK =2, COS =9.

Metrics for Object-Relotional Databases

An object-relational database schema is

composed of a number of tables related by referential integrity, which have columns that can be defined over simple or complex (user-defined) data types. We define the next metrics for objectrelational databases ([4J):

Schema Si~e(SS)

We define the size of a system as the sum of the size of every table (TS) in the schema:

The table size (TS) measures the size not only

in terms of the simple columns (defined using simple domains) bot also in terms of complex columns (defined using user-defined classes).

Formally it can be defined as the sum of the total

size of the simple columns (TSSC) and the total size of the complex columns (TSCC) in the table. TSSC is simply the number of simple columns in the table (considering that each simple domain has a size equal to one). TSCC is defined as the sum of complex columns size (CCS). The size of a complex column is no more than the size of the class hierarchy above the columnand is defined as weighted by the number of complex columns which use the hierarchy. Finally, the size of a class hierarchy is defined as the sum of the size of each class on the hierarchy. For more details about the precise definition of this metric see [4J.

Complexz"tyof references between tables (DRT, NFK)

In object-relational databases, other characteristicsof relational databasesare preserved. Metrics related with the referential integrity, such as NI:;Kand DRT proposed in the previous section, can also be used.

We can apply these metrics to the following example:

CREATE TYPE projectAS ( name CHAR(10), budget FLOAT);

This relational database schema representedas a relationalgraph(see figure 3). can be

Fiooure3. Relational graphfor the example

CREATE TYf E employee AS (

emp_num INTEGER, level INTEGER, salary_base FLOAT, proj project) method calc_salary()

RETURNS DECIMAL(72));

Name data

SHOT type

ROJECT

EMPLOYE

Then, the values for the other metrics are: SHC = 6, CCS = 3, TSCC = 6, TSSC - 2, TS = 8, SS 8.

Mebies for Active Databases

Whenmeasuring active databases,we can make use of the notion of a triggering graphas defined in [I]. A triggering graph is a pair <S, L> where S representsthe set of ECA rules, and L is a set of directedarcs where an arc is drawnfrom Si to Sj if Sis action causes the happening of an event occurrence that participates in Sjs events. This notion of triggering graphis modified by [71 in two aspects. Firstly, arcs are weighted by the numberof potential event occurrences produced by the triggering rule Ci.e.Si) that could affect the rule triggered off (i.e. Sjs event). Secondly, the nodes S are extended with the set of transactionsT. A transactionis an atomic set of (database) actions where any of these actions could correspondto an event triggering one or more rules. Therefore, T nodes will have outgoing links but never incoming links, as we assume that a transactioncan never be triggered from within a rules action or another transaction.

The active databasecouldbe characterisedby the followingtriggeringgraphmeasures([ 8 ]): . NA the minimum number of anchors required to encompass the whole set of potential causes of Si. An anchor is a transaction node of the triggering graph, which has a link (either directly or transitively) with at least one cause of Si.

D, the distance.This measure correspondsto the length of the longest path that connects Si with any of its anchors.

TP, the triggering potential. Given a triggeringgraph < S, L >, and a node of the graph, ruleSi, 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 quotientbetween the number of potential causes of Si, and Sis event cardinality~ CREATETRIGGERONE AFTERDELETEON TABLE3 FOREACH ROW WHEN(OLD.NUMBER=3) BEGIN

DELETEFROMTABLE4 WHERETABLE4.S#=:TABLE3"J#; END ONE; CREATETRIGGERTWO AFTERDELETEON TABLE4 FOREACH ROW WHENCOLD.NAME=.SMITH) BEGIN

DELETEFROMTABLE5 WHERETABLE4.S#=:OLD.S#: END TWO;

For trigger ONE, NA = I, TP = I and D = I, for trigger TWO, NA = 1, TP = 1, and D = 2.

4. Metrics Formaf VaRdation

There are two main tendencies in metrics validation: the frameworks based on axiomatic approachesand the ones based on the measurement theory. The goal of the first ones is merely definitional~On this kind of formal framework, a set of formal properties is defined for a given software attribute and it is possible to use this propertyset for classifying the proposedmeasures.

The most well-known frameworks of this type are those proposedby [351, [ 3 ], and [ 25 ]. The main goal of axiomatisationin software metrics research is the clarification of concepts to ensure that new metrics are in some sense valid. The measurement theorybased frameworks (such as [37} or {36]) specify a general framework in which measures should be defined,Measurement theory gives clear definitions of terminology, a sound basis of software measures, criteria for experimentation, conditions for validation of software measures, foundations of prediction models, empirical properties of software measures, and criteria for measurementscales. The discussion of scale types is importantfor statisticaloperations.

In this section, we will present the results of the formal verification of the presented metrics with R E L V E N A L

NFK DRT NA COS SS TS NA TP D

BRIANO ET

AL(1996) COMPLEXHY

ABOVE THE ORDINA LENGT

ABOVE THE ORDINAL SLZ 512 SIZ SIZE

ABOVE THE ORDINA

RATIO ABOVE THE ORDINA

ABOVE THE ORDINA COMPLEXITY

ABOVETHE ORDINA

NOT CLASSIPIAB

ABOVE THE ORDINA LENGT

ABOVE THE ORDINA With the axiomatic approach results we can know, for example for relational databasesthat we need some metrics for capturing cohesion and coupling and covering all the characteristics defined by the framework From the measurement theory results we can know what kind of operations it is possible to make with the defined metrics,the statistics that it is possible to apply to them etc.

5. Metrics Empirical VaBdaHon

In the past, empirical validation bas been an informal process relying on the credibility of the proposer. Often , when a measure was identified theoreticallyas an effective measure of complexity, practitioners and researchers began to use the metric without questioning its validity. Today, many researchers and practitioners assume that validation of a measure (from a theoretical point of view) is not sufficient for widespread acceptance. They expect the empiricalvalidation to demonstrate that the measure itself can be validated. Useful 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 testingthe hypothesis ([10]).

In the rest of this section, we summarize differentexperimentsthat we have done with some of the metrics discussed in this chapter.All of these initial experimentsrequire further experimentation in order to validate the findings. However, these results can be useful as a starting point for future research.

A complete description of the experiments can be found in [ 5 ] for relational database metrics, in [ 27 ] for object-relationalones and in [ 8 ] for active ones.

Relational experiment

Our objective was to demonstrate that the metrics related with referential integrity (DRT and ) can be used for measuring the complexity of the relational database schema, which influences in the relational database understandability. The participants of this study were computer science students at the University of Castilla-La Mancha (Spain), who were enrolled in a two-semester 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 the length of the referential tree. This metric is not relevant by itself, but can modulate the effect of the number of foreign keys in a database system

Object-relational experiment

Five object-relational databases were used in this experiment with an average of 10 relations per database. Five subjects participated in the experiment. All of them were experienced in both relational databases and object-oriented programming. To analyze the usefulness of the metrics, we used two techniques: C4.5 ([ 30 ]), a machine learning algorithms, and RoC ([ 31 ]), a robust Bayesian classifier. In conclusion, both the techniques discover that the table size is a good indicator for the understandability of a table. The depth of the referential tree is also presented as an indicator by C4.5 but not clearly by RoC. The number of foreign keys does not seem to have a real impact on the understandability of a table.

Active experiment

Our objective was to assess the influence of D

and TP in rule interaction understandability.

However, such understanding could be influenced

by how the reasoning is conducted.As rules can be seen as cause-and-effectlinks, two questions can be posed by the user: "whateffects can a rule produce (forward reasoning)?" or "how can an effect be produced (backwardreasoning)?".The participants of the experimentwere final-year computerscience students at the University of the Basque Country, who were enrolled in an advance database course The students were already familiar with relational database, and some laboratories were previously conducted on the definition of triggers. For the forward experiment, we concluded that the triggering potential in a databaseschema is a solid indicator of its understandability, and that the distance is not relevant by itself and cannot modulate the effect of the triggeringpotential. For the backward experiment we concluded that both metrics are solid indicatorsof its understandability.

All the experiments described need to be replicated in orderto obtainmore consistentresults. However, controlled experiments made in a laboratoryare useful as a startingpoint but present some problemssuch a the large numberof variables that can cause differences- Therefore, it is convenient to also run case studies working with real data.

6. Conclusions and Future Work

Databasesare becoming more complex, and it is necessary to measureschemata complexity in order to understand, monitor, control, predict and improve database development and maintenance projects. Database metrics could help designers, choosing between alternative semantically equivalent schemata, to select the most maintainable one and understandtheir contribution to the overallIS maintainability.

We have put forward different measures (for internal attributes) in order to measure the complexity that affects the maintainability (an external attribute)of the relational,object-relational and active databaseschemas.

However it is not enough to propose the metrics, a formal validation is also needed for knowing their mathematical characteristics. We have presentedthe two main tendencies in metrics formal validation, axiomatic approaches and measurement theory. Although the information obtainedfrom both techniquesis different,the final objective is the same, to obtain objective mathematical information of the metrics we are workingon.

However, as we have indicated previously, research into software measurement is needed also from a practical point of view. We have presented some of the experiments that we have developed for the different kinds of databases. Nevertheless controlledexperimentshave problems (like the large number of variables that causes differences) and limits (they do not scale up, are done in a class in training situations, are made in vitro and face a variety of threats of validity). Thereforeit is convenient to run multiple studies, mixing controlledexperimentsand case studies. For these reasons, a more in depth empirical evaluation is under way in collaboration with industrial and public organizationsin "rear situations.

ACKNOWLEDGEMENT

This research is part of the MANTICA project,

partially supported by the CICYT and the European

Union (CICYT-1FD97-0168) and by the CALIDAT project carried out by Cronos Iberica (supported by the Consejeria de Educaci6n de la Comunidad de Madrid, Nr, 09/0013/1999)

References

1- Aiken , A. , Hellerstein , J.M. and Widow , J. ( 1995 ). Static analysis techniques for predicting the behaviour of active database rules . ACM Transactionson Databases , 20 ( 1 ), 341 .

.?. Batra , D. , Hoffer , J.A. and Bostrom , R.P. ( 1990 ). A comparison of user performance between the relational and the extended entity relationshipmodels in the discovery phase of databasedesign . CACM , 33 ( 2 ), 126 139 .

3. Briand , L.C. , Morasca , S. And Basin , V. ( 1996 ). Property-based software engineering measurement . IEEE Transactionson Software Engineering ,Vol. 22 ( 1 ). pp~ 68 - 85 .

4. Calero , C` , Piattini , M , Ruiz , F ~and Polo , M. ( 1999 ) Validation of metrics for Object" Relational Databases, InternationalWorkshop on QuantitativeApproaches in Object-Oriented Software Engineering (ECOOP99 ), Lisbon (Portugal), 14 - 18June

5. Calero , C. , Piattini , M , Genero, M. , Serrano , M. and Caballero , I. ( 2000 ). Metrics for Relational Databases Maintainability, .CKAI52000, Cardiff,UK.

6. Date ., C.J. ( 1995 ). An Introductionto Database Systems . 6th. Addison-Wesley , Reading, Massachusetts-

7. Diaz, 0 . and Piattini, M ( 1999 ). Metrics for active databases maintainability . CAISE99 . Heidelberg,June 1618.

8. Dfaz . O., Piattini . M y Calero, C. ( 2001 ). Measuring active databases maintainability . Accepted for publication in Information Systems Journal

9. Fenton , N. ( 1994 ). Software Measurement:A Necessary Scientific Basis . IFRE Transactions on SoftwareEngineering , 20 ( 3 ), 199 - 206 .

1O. Fenton , N , andPfJeeger S.L. ( / 997). Software Metrics: A Rigorous Approach 2nd. edition . London, Chapman& Hall.

ll" Frazer , A. ( 1992 )~ Reverse engineering-hype, hope or here? . In; P. A.V. Hall , Software Reuse andReverse Engineering in Practice. Chapman &Hall.

12. Glass , R. ( 1996 ). The Relationship Between Theory and Practice in Software Engineering. Software, November , Vol. 39 ( 11 ). pp 11 - 13 , Gray R.ff.M. , Carey B.N. , McGlynn N.A. , Pengelly A.D. , ( 1991 ), Design metrics for databasesystems . BT Technology J , Vol 9 , 4 Oct.pp. 69 - 79

14. Henderson-Sellers , B- ( 1996 ). Object-Oriented Mefrics - Measures of CompJexity .PrenticeHall, UpperSaddle River, New Jersey.

15. ISO, ( 1994 ). Software Product Evaluation QualityCharacteristicsand Guidelines for their Use . ISO/IECStandard9126 , Geneva.

16. Jarvenpaa , S. and Machesky , J ~ ( 1986 ). End user learningbehaviorin data analysis anddata modeling tools . Proc. of the 7th Int. Conf. on InformationSystems, SanDiego , 152 - 167 .

17. Juhn , S. and Naumann , J. ( 1985 ). The effectiveness of data representation characteristicson user validation . Proc. of the 6th Int. Conf. on Information Systems , Indianapolis, 212 - 226 .

18. Kim , Y.G. and March , S.T. ( 1995 ). Comparing Data Modeling Forrnalisms~ CACM38(6 ), / 03 -1 15 .

19. Li , HF. and Cheng,W.K. ( 1987 ). An empirical study of software metrics . IEEE Trans. on SoftwareEngineering , 13 ( 6 ), 679 - 708 ~

20. MacDonell , S.G. , Shepperd, MJ. and Sallis , P "J.( 1997 ). Metrics for Database Systems; An Empirical Study . Proc. Fourth International Software Metrics Symposium - Metrics'97 , Albuquerque .IEEE ComputerSociety, 99 - 107 .

21. McCabe , T.J. ( 1976 ). A complexity measure . IEEE Trans. Software Engineering 2 ( 5 ), 308 - 320 .

22. McClure , C. ( 1992 ) The Three Rs of Software Automation: Reengineering, Repository, Reusability .Englewood Cliffs: Prentice-Hall. Melton , A . (ed.) ( 1996 ). Software Measurement .London, InternationalThomson ComputerPress.

24. Moody, D~ L. ( 1998 ). Metrics for Evaluating the Quality of Entity Relationship Models . Proc. of the Seventeenth International Conference on Conceptual Mode|ling (ER'98) , Singapore.

25. Morasca , S, and Briand , I .C. ( 1997 ). Towards a Theoretical Framework for measuring software attributes . Proceeding of the Fourth International,Software Metrics Symposium , 119 - 126 .

26. Pf|eager, S. L. ( 1997 ). Assessing Software Measurement . IEEE Software. March/April , 25 - 26 .

27. Piattini , M. , Calero , C. , Sahraoui , H. and Loams , H. ( 2000 ) An empirical Study with object-relational database metrics, ECOOP:2OOOC,annes , I3 June.

28. Piattini , M. , Genera , M, , Calero , C. , Polo , M. and Ruiz , F. ( 2001 ). Metrics for Managing Quality in InfOrrnation Mode|ling . In: "Information Modeling in the New MiJJennium"M. Rossi andK . Siau (eds.) , Idea GroupPublishing ,USA.

29. Pigoski , T.M. ( 1997 ). Practical Software Maintenance . Wiley Computer Publishing. New York, USA.

30. Quinlan , J.R. . C4 . 5: Programs for Machine Learning , ( 1993 ), Morgan Kaufmann Publishers.

31. Barnaul , M. and Sebastiani , P. Bayesian methods for intelligent data analysis . In M Berthold and D.J . Hand, editors, An Introductionto Intelligent Data Analysis , (New York, 1999 ). Springer.

32. Rossi , M. and Brinkkemper , S. ( 1996 ). Complexity Metrics for Systems Development Methods and Techniques . InformationSystems 21 ( 2 ), 209 - 227 .

33. Shoval , P. and Even-Chaime , M ( 1987 ). Database schema design: An experimental comparison between normalization and informationanalysis . Database 18 ( 3 ), 3039 .

34 " Sneed , H.M andFoshag. O. ( 1998 ). Measuring Legacy Database Structures . Proc of The European Software Measurement Conference FESMA 98 , Antwerp ,May 6-8, Coombes, Van Huysduynen andPeelers (eds.), 199 - 211 .

35. Weyuker , E.J. ( 1988 ). Evaluating software complexity measures . IFFE Transactions on Software Engineering Vol. 14 ( 9 ). pp. 1357 - 1365 .

36. Whitmire , S.A. ( 1997 ), Object OrientedDesign Measurement,Ed. Wiley.

37. 2use, H. ( 1998 ). A Framework of Software Measurement .Berlin, Walter de Gruyter