Disjunctive Logic Programming with types and objec

INFSYSResearhReportInstitutfurInformationssystemeAbtg.WissensbasierteSystemeTehnisheUniversitatWienFavoritenstrae9-11A-1040Wien,AustriaTel:[phone]Fax:[phone]sekkr.tuwien.a.aturInformationssystemeAbteilungWissensbasierteSystemeDisjuntiveLogiProgrammingwithTypesandObjets:TheDLV+SystemFranesoRiaNiolaLeoneINFSYSResearhReport1843-05-10Otober2005INFSYSResearhReportINFSYSResearhReport1843-05-10,Otober2005DisjuntiveLogiProgrammingwithTypesandObjets:TheDLV+SystemFranesoRia1NiolaLeone1Abstrat.ThepaperpresentsDLV+,aDisjuntiveLogiProgramming(DLP)systemwithobjet-orientedonstruts,inludinglasses,objets,(multiple)inher-itane,andtypes.DLV+isbuiltontopofDLV(astate-of-theartDLPsystem),andprovidesagraphialuserinterfaethatallowstospeify,update,browse,query,andreasononknowledgebases.Twostrongpointsofthesystemarethepowerfultype-hekingmehanismandtheadvanedinterfaeforvisualquerying.DLV+isalreadyusedforthedevelopmentofknowledgebasedappliationsforin-formationextrationandtextlassiation.1DepartmentofMathematis,UniversityofCalabria.87030Rende(CS),ItalyE-mail:ria,leonemat.unial.itCopyright2005bytheauthors2INFSYSRR1843-05-101IntrodutionDisjuntiveLogiProgramming(DLP)isanadvanedformalismforKnowledgeRepresen-tationandReasoning(KR&R)(11).DLPisveryexpressiveinapreisemathematialsense:itisabletoexpressallproblemsbelongingtotheomplexitylassP21.Moreover,theavailabilityofapairofeÆientDLPsystems,likeDLV(16),GnT(13)and,morereently,thedisjuntiveversionofCmodels(17)makeDLPapowerfultoolfordevelopingadvanedknowledge-basedappliations(3;18).ThereentappliationofDLPintheareasofKnowledgeManagement(KM),Seurity,andInformationIntegration(15;19),hasonrmed,ontheonehand,theviabilityoftheDLPexploitation.Ontheotherhand,ithasevidenedsomelimitationsofDLPlanguageandsystems.Asfarasthelanguageisonerned,theneedtorepresentomplexreal-worldentities,likelasses,objets,ompoundobjets,andtaxonomies,hasemerged(19).Moreover,DLPsystemsaremissingtoolsforsupportingtheprogrammers,liketype-hekersandeasy-to-usegraphialenvironments,tomanagethelargeandomplexdomainstobedealtwithinreal-worldappliations.ThispaperdesribestheDLV+system,arststeptowardstooverometheabovelimita-tions.Itisaross-platformdevelopmentenvironmentforknowledgemodelingandadvanedknowledge-basedreasoning.TheDLV+systemallowsforthedevelopmentofomplexappli-ationsandallowstoperformadvanedreasoningtasksinauserfriendlyvisualenvironment.TheDLV+systemseamlesslyintegratestheDLVsystem(16)exploitingthepowerofastableandeÆientDLPsolver.Astrongpointofthesystemisitspowerfullanguage,extendingDLPbyobjet-orientedfeatures.Inpartiular,thelanguageinludes,besidestheoneptofrelations,theobjet-orientednotionsoflasses,objets(lassinstanes),objet-identity,omplexobjets,(multiple)inheritane,andtheoneptofmodularprogrammingbymeansofreasoningmodules.Alassanbethoughtofasaolletionofindividualsthatbelongtogetherbeausetheysharesomefeatures.Anindividual,orobjet,isanyidentiableentityintheuniverseofdisourse.Objets,alsoalledlassinstanes,areunambiguouslyidentiedbytheirobjet-identier(oid)andbelongtoalass.Alassisdenedbyaname(whihisunique)andanorderedlistofattributes,identifyingthepropertiesofitsinstanes.Eahattributehasanameandatype,whihis,intruth,alass.Thisallowsforthespeiationofomplexobjets(objetsmadeofotherobjets).Classesanbeorganizedinaspeializationhierarhy(ordata-typetaxonomy)usingthebuilt-inis-arelation(multipleinheritane).Relationshipsamongobjetsarerepresentedbymeansofrelations,whih,likelasses,aredenedbya(unique)nameandanorderedlistofattributes(withnameandtype)2.AsinDLP,logiprogramsaresetsoflogirulesandonstraints.However,DLP+extends1ThelassofalldeisionproblemssolvableinnondeterministipolynomialtimebyaTouringmahinewithanoraleinNP.2Notethat,unlikeobjets,relationinstanesarenotidentiedbymeansofoid’s.INFSYSRR1843-05-103thedenitionoflogiatombyintroduinglassandrelationprediates,andomplexterms(allowingforadiretaesstoobjetproperties).Thisway,DLP+rulesmerge,inasimpleandnaturalway,thedelarativestyleoflogiprogrammingwiththenavigationalstyleoftheobjet-orientedsystems.Inaddition,DLP+logiprogramsareorganizedinreasoningmodules,takingadvantageofthebenetsofmodularprogramming.Importantly,thestrongly-typednatureofDLP+allowedfortheimplementationofanumberoftype-hekingroutinesthatverifytheorretnessofaspeiationonthey,resultinginanhelpfortheprogrammer.Moreover,DLV+oersseveralimportantfailitiesdrivingthedevelopmentofboththeknowledgebaseandthereasoningmodules.UsingDLV+,developersanddomainexpertsanreate,edit,navigateandqueryobjet-orientedknowledgebasesbyaneasy-to-usevisualenvironment,enrihedbyagraphiqueryinterfaealaQBE.Inshort,theontributionofthepaperistwofold:Wedeneanewlanguage,namedDLP+,forKnowledgeRepresentationandReasoning,extendingDLPwithrelevantonstrutsoftheobjet-orientedparadigm,likeClasses,Types,ObjetsandInheritane.WeprovideaformaldenitionofbothsyntaxandsemantisofDLP+,andillustrateitsknowledgemodelingfeaturesbyexamples.WeanalyzetheomputationalomplexityofthemaindeisionalproblemsarisingintheontextofDLP+.Wedesign