摘要
Graphsarewidelyusedformodelingcomplicateddatasuchassocialnetworks,chemicalcompounds,proteininteractionsandsemanticweb.Toeffiectivelyunderstandandutilizeanycollectionofgraphs,agraphdatabasethatefficientlysupportselementaryqueryingmechanismsiscruciallyrequired.Forexample,SubgraphandSupergraphqueriesareimportanttypesofgraphquerieswhichhavemanyapplicationsinpractice.Aprimarychallengeincomputingtheanswersofgraphqueriesisthatpair-wisecomparisonsofgraphsareusuallyhardproblems.Relationaldatabasemanagementsystems(RDBMSs)haverepeatedlybeenshowntobeabletoefficientlyhostdifferenttypesofdatasuchascomplexobjectsandXMLdata.RDBMSsderivemuchoftheirperformancefromsophisticatedoptimizercomponentswhichmakeuseofphysicalpropertiesthatarespecifictotherelationalmodelsuchassortedness,properjoinorderingandpowerfulindexingmechanisms.Inthisarticle,westudytheproblemofindexingandqueryinggraphdatabasesusingtherelationalinfrastructure.Wepresentapurelyrelationalframeworkforprocessinggraphqueries.Thisframeworkreliesonbuildingalayerofgraphfeaturesknowledgewhichcapturemetadataandsummaryfeaturesoftheunderlyinggraphdatabase.Wedescribedifferentqueryingmechanismswhichmakeuseofthelayerofgraphfeaturesknowledgetoachievescalableperformanceforprocessinggraphqueries.Finally,weconductanextensivesetofexperimentsonrealandsyntheticdatasetstodemonstratetheefficiencyandthescalabilityofourtechniques.
出版日期
2010年06月16日（中国期刊网平台首次上网日期，不代表论文的发表时间）
