From extensional to intensional knowledge Inductiv

FromExtensionaltoIntensionalKnowledge:InductiveLogicProgrammingTechniquesandTheirApplicationtoDeductiveDatabasesPeterA.FlachDepartmentofComputerScience,UniversityofBristolMerchantVenturersBuilding,WoodlandRoad,BristolBS81UB,[e-mail],flach/Abstract.Thischapteraimsatdemonstratingthatinductivelogicpro-gramming(ILP),arecentlyestablishedsubeldofmachinelearningthatinducesrst-orderclausaltheoriesfromexamples,combinesverywellwiththeareaofdeductivedatabases.Inthecontextofdeductivedatabases,inductioncanbedenedasinferenceofintensionalknowledgefromextensionalknowledge.Classication-orientedILPapproachescor-respondtoinductionofviewdenitions(IDBrules),whiledescription-orientedILPapproachescorrespondtoinductionofintegrityconstraints.TheapplicabilityofILPmethodsindeductivedatabasesthusincludesinductionofIDBrulesandlearningofintegrityconstraints.Furtherpos-sibleapplicationsarereverseengineering,queryoptimisationandinten-sionalanswers,anddatamining.Thechaptergivesanaccessibleintro-ductiontoILPwithparticularemphasisonapplicationsindeductivedatabases.1IntroductionConsiderthefollowingextensionaldatabase,deningthebinarypredicatess/2andm/2:s(su,su).s(su,pe).m(mi,pa).s(ro,pe).s(pe,ro).m(ma,pe).s(ro,su).s(pa,pa).m(ma,su).s(pe,pe).s(pe,su).m(ma,ro).s(ro,ro).s(su,ro).Thereaderisinvitedtotakeaminutetotryandmemorisethesetwoextensionalrelationsbeforereadingon.Whenattemptingtomemorisetheserelationsyouwereprobablylookingforregularitieswithintheextensions,orrelationsbetweenthem.Forinstance,youprobablyhavenoticedthats/2isreflexive.Maybeyouhavealsodiscoveredthats/2issymmetric.Andifyouarereallyclever,youmayhaveseenthats/2isanequivalencerelation,sinceitistransitiveaswell!Ifyouwerelookingforrelationsbetweens/2andm/2,youmayhavefurthernoticedthatpe,suandroallareB.Freitagetal.(Eds.):TransactionsandChangeinLogicDBs,LNCS1472,pp.356{387,1998.cSpringer-VerlagBerlinHeidelberg1998InductiveLogicProgrammingTechniques357m-relatedtoma,butpaism-relatedtomi.Youmayevenhavediscoveredthats/2canbedenedintermsofm/2:s(X,Y):-m(M,X),m(M,Y).Noticethattherstargumentofm/2canbeseenasenumeratingtheequivalenceclassesofs/2.Thatis,evenifconcentratingonregularitieswithins/2andignoringm/2,youcouldhaveconcludedthatthereexistbinarypredicatesintermsofwhichs/2canbedenedbymeansofaclausesimilartotheoneabove.Wehavejustseensomesimpleexamplesof`intensionalising'extensionallydenedpredicates.Sinceextensionalrelationscanbeseenascollectionsofin-stances,andintensionalrulesasgeneralhypotheses,theprocessofderivingintensionalfromextensionalrelationscanbeseenasaformofinduction,orlearningfromexamples.Inductivelogicprogramming(ILP)isaformofinduc-tivelearningthatemploysclausallogicasarepresentationformalism,andthusiswell-suitedtointensionalisingextensionalrelations.Thepotentialofapply-ingILPtechniquesinthecontextofdeductivedatabaseshashoweverhardlybeenexplored.ThischapterthereforeaimsatprovidinganintroductiontoILP,aswellasindicatingpossibleapplicationareasforILPtechniquestodeduc-tivedatabases.Broadlyspeaking,wemayemployILPtechniquesindatabasedesign(reverseengineering),inqueryprocessing(optimisationandintensionalanswers),andinknowledgediscovery(inductivequeries).Howdoesinductivelearningindeductivedatabasestintothepictureofdatabasedynamics?Thisdependspartlyuponthenatureoftheextensionaldatathatformsthestartingpointforlearning.Ifthisdataiscomplete,asintheaboveexample,inductivelearningmainlyindicatesredundancyinthedata,andhowtotranslateredundancyintostructure.WewillencounterthisformofinductiveknowledgebaserestructuringinSection3below,whenwediscussinductionoffunctionalandmultivalueddependencies.However,suchcompletenessofextensionaldataisnotaprerequisiteforin-duction,sinceinductivehypothesesaretypicallypredictive,therebycompletingtheextensionaldata.Forinstance,theaboveclausemaystillbefoundifsomeofthefactsfors/2aremissing(clearly,theClosedWorldAssumptionisinap-propriateinsuchacase).InthiscasewearesynthesisingpartoftheIDBfromincompleteextensionalspecications.Theseexamplesservetoillustratethatinductivelearningcanbeseen,ontheonehand,asanequivalence-preservingtransformationprocess,andontheotherhand,asageneralisingrevisionprocess.Thechapterisstructuredasfollows.InSection2weprovideagentlein-troductiontoinductivelogicprogramming,concentratingonthemainconceptsandprovidingmanyexamples.Iproceedtodescribemypreviousworkonin-ductiveknowledgebaserestructuringasacase-studyoftheapplicationofILPtechniquestodatabasesinSection3.Section4discussespossibilitiesfortightintegrationbetweenanILPmoduleandaDDBMS.Weendthechapterwithsomeconcludingremarks.358PeterA.Flach2InductiveLogicProgrammingInductivelogicprogramminghasitsrootsinconceptlearningfromexamples,arelativelystraightforwardformofinductionthathasbeenstudiedextensivelybymachinelearningresearchers.Theaimofconceptlearningistodiscover,fromagivensetofpre-classiedexamples,asetofclassicationruleswithhighpredictivepower.Formanyconceptlearningtasks,so-calledattribute-valuelanguageshavesucientrepresentationalpower.Anexampleofa