A uniform framework for concept definitions in des

JournalofArticialIntelligenceResearch6(1997)87-110Submitted7/96;published3/97AUniformFramework[e-mail]\LaSapienzaViaSalaria113,00198Roma,[e-mail]\LaSapienzaViaSalaria113,00198Roma,ItalyAbstractMostmodernformalismsusedinDatabasesandArticialIntelligencefordescribinganapplicationdomainarebasedonthenotionsofclass(orconcept)andrelationshipamongclasses.Oneinterestingfeatureofsuchformalismsisthepossibilityofdeningaclass,i.e.,providingasetofpropertiesthatpreciselycharacterizetheinstancesoftheclass.Manyrecentarticlespointoutthatthereareseveralwaysofassigningameaningtoaclassdenitioncontainingsomesortofrecursion.Inthispaper,wearguethat,insteadofchoosingasinglestyleofsemantics,weachievebetterresultsbyadoptingaformalismthatallowsfordierentsemanticstocoexist.Wedemonstratethefeasibilityofourargument,bypresentingaknowledgerepresentationformalism,thedescriptionlogicALCQ,withtheabovecharacteristics.Inadditiontotheconstructsforconjunction,disjunction,negation,quantiers,andqualiednumberrestrictions,ALCQincludesspecialxpointconstructstoexpress(suitablyinterpreted)recursivedenitions.Theseconstructsenabletheusualframe-baseddescriptionstobecombinedwithdenitionsofrecursivedatastructuressuchasdirectedacyclicgraphs,lists,streams,etc.WeestablishseveralpropertiesofALCQ,includingthedecidabilityandthecomputationalcomplexityofreasoning,byformulatingacorrespondencewithaparticularmodallogicofprogramscalledthemodalmu-calculus.1.IntroductionMostmodernformalismsusedinDatabasesandArticialIntelligenceforrepresentinganapplicationdomainarebasedonthenotionsofclass(orconcept)andrelationshipamongclasses.Forexample,theobject-orientedandsemanticsdatamodelsdevelopedinDatabasesdescribedataintermsofclasses(sometimescalledentitytypes)andincorporateseveralfeaturesforestablishingvariousformsofrelationshipsbetweenclasses.Ontheotherhand,thenotionofclass(oftencalledconceptorframe)andthatoflinkamongclassesareprovidedinallstructuredformalismsforKnowledgeRepresentation(frame-basedlanguages,semanticnetworks,descriptionlogics,etc.).Finally,thisnotionisalsopresentinseveraltypesystemsofprogramminglanguages,speciallythosebasedontheobject-orientedparadigm.Therearebasicallytwowaysofusinganddescribingclasses(concepts).Intherstone,whichwecancalltheprescriptiveapproach,thedescriptionformalismallowsforexpressinganumberofpropertiesofaclass,thusprescribingconstraintsthattheinstancesoftheclassmustsatisfy.Inthesecondone,whichwecancallthedenitionalapproach,theformalismallowsforprovidingthedenitionofaclass,i.e.,asetofpropertiesthatpreciselycharacter-c1997AIAccessFoundationandMorganKaufmannPublishers.Allrightsreserved.DeGiacomo&Lenzeriniizetheinstancesoftheclass.Whiletheprescriptiveapproachisquitewellunderstoodandestablished,thedenitionalapproachisstillthesubjectofaninterestingdebate,regardingbothitsnatureanditssemanticfoundation.Inparticular,itiswellknownthattherearevariouswaystoassignameaningtoaclassdenitionwhenitcontainssomesortofrecursion(Baader,1990,1991;Nebel,1991;Beneventano&Bergamaschi,1992;Beeri,1990).Inthispaper,weareconcernedwiththesemanticproblemsrelatedtothedenitionalapproach,arguingthat,insteadofchoosingasinglestyleofsemanticsfortheknowledgerepresentationformalism,weachievebetterresultsbyallowingdierentsemanticstocoex-ist.WediscussthisissueinthecontextofDescriptionLogics1,whicharelogicsoriginallydevelopedinKnowledgeRepresentationtoprovideaformalreconstructionofframe-basedlanguages.Descriptionlogicsdescribethedomainofinterestintermsofconcepts,whichrepresentclassesofindividuals,androles,whicharebinaryrelationsusedtospecifyproper-tiesorattributesofindividualsaswellaslinkswithotherindividuals(Nebel,1990).Startingfromatomicconcepts,denotedsimplybyaname,morecomplexconceptsarebuiltbyus-ingasuitablesetofconstructs.Forexample,theexpressionparentumaleu8child:maledenotestheconceptoffather(maleparent)whosechildrenareallmale.Thesymboludenotestheconstructforconceptconjunction,while8denotesuniversalrolequantication.Typically,conceptsarestructuredintohierarchiesdeterminedbythepropertiesassociatedwiththem.Thehierarchicalstructureisdenedinsuchawaythatmorespecicconceptsinheritthepropertiesofthemoregeneralones.Weintroduceadescriptionlogic,calledALCQ,whichextendsthewell-knownde-scriptionlogicALC(Schmidt-Schau&Smolka,1991)byincludingthesocalledqualiednumberrestrictions,whichareaverygeneralformofcardinalityconstraintsonroles,andspecialxpointconstructs,whichenableustocapturethevarioussemanticsforrecursivedenitionswithinasingleformalism.Notably,theavailabilityoftheseconstructsmakesitpossibletocombinetheusualframe-baseddescriptionswithdenitionsofrecursivedatastructuressuchasdirectedacyclicgraphs,lists,streams,etc.WeestablishseveralpropertiesofALCQ,includingthedecidabilityandthecompu-tationalcomplexityofreasoning,byformulatingacorrespondencewithaparticularmodallogicofprogramscalledthemodalmu-calculus.Recentarticles,(e.g