No1图数据库课程引论部分

Instructor:ZOU’leizoulei@北京大学计算机科学技术研究所InstituteofComputerScienceandTechnologyofPekingUniversityGraphDataManagement1No1图数据库课程引论部分共30页，您现在浏览的是第1页!OutlineApplicationsandChallengesofGraphDataExitingGraphDatabaseSystemsAboutthecourse2No1图数据库课程引论部分共30页，您现在浏览的是第2页!OutlineApplicationsandChallengesofGraphDataManagementExitingGraphDatabaseSystemsAboutthecourse3No1图数据库课程引论部分共30页，您现在浏览的是第3页!SomeChallengesinLargeGraphDataManagementAnExample：ConsideringaSNSwebsite,therearemorethan1billionactiveusers.Query:Iwanttoknowwhether“TomisafriendofJack,orafriendofhisfriends…?”PossibleSolutions:(Storage)Storetheconnectionsbetweenindividualsinarelationaltable(Query)PerformSelf-joinRecursively….4No1图数据库课程引论部分共30页，您现在浏览的是第4页!NetworkMotifs:SimpleBuildingBlocksofComplexNetworks(R.Milo,etal.@SCIENCE03)5No1图数据库课程引论部分共30页，您现在浏览的是第5页!10December20226FrequentSubgraphPatternMining(A)(B)(C)GraphDatasetFrequentPatterns(minsupportis2)(1)(2)No1图数据库课程引论部分共30页，您现在浏览的是第6页!7ReachablilityQuery123467859131011121415?Query(1,11)

Yes?Query(3,9)

NoNo1图数据库课程引论部分共30页，您现在浏览的是第7页!RDFDataManagementThe

ResourceDescriptionFramework(RDF)

isafamilyof

WorldWideWebConsortium

(W3C)

specificationsoriginallydesignedasa

metadata

datamodel.8WWWWebofPagesSemanticWebWebofDataNo1图数据库课程引论部分共30页，您现在浏览的是第8页!AnRDFDataExample9No1图数据库课程引论部分共30页，您现在浏览的是第9页!SPARQLQueryQuery:FindallindividualswhowerebornonFeb.12,1809anddiedonApril.15,1865.SPARQLSyntaxSelect?nameWhere{?m<hasName>?name.?m<BornOnDate>“1809-02-12”.?m<DiedOnDate>“1865-04-15”.}QueryGraph10No1图数据库课程引论部分共30页，您现在浏览的是第10页!OutlineApplicationsandChallengesofGraphDataExitingGraphDatabaseSystemsAboutthecourse11No1图数据库课程引论部分共30页，您现在浏览的是第11页!SomeExistingGraphDatabaseSystemsNeo4j

-anopen-source/mercial(AGPLv3)graphdatabaseDEX

-Ahigh-performancegraphdatabaseandsoon…InternationalGraphDatabaseWorkshops:

./IWGD2010/index.html..au/~gdm2011/12No1图数据库课程引论部分共30页，您现在浏览的是第12页!Neo4jAPIAnExampleprivate

void

printFriends(Nodeperson){

Traversertraverser=person.traverse(

Order.BREADTH_FIRST,//Traverse图的模式

StopEvaluator.END_OF_GRAPH,//Traverse图的停止条件

ReturnableEvaluator.ALL_BUT_START_NODE,//哪些图节点被返回

MyRelationshipTypes.KNOWS,//按照那些边来进行Traverse

Direction.OUTGOING);//Traverse的方向

for

(Nodefriend

:traverser)

{

System.out.println(friend.getProperty(

"name"

));

}}13No1图数据库课程引论部分共30页，您现在浏览的是第13页!CourseContentGraphMining-frequentsubgraphminingIndexing&QueryProcessing-reachablilityquery-shortestpathquery-subgraphquery

-keywordsearchRDFDataManagement-Indexing&SPARQLQueryProcessing

14No1图数据库课程引论部分共30页，您现在浏览的是第14页!课程考核课堂报告（30%）

每位学生报告一篇数据库领域(含数据挖掘，信息检索相关领域)顶级论文

（20分钟+5分钟提问）作业（30%）3项作业，完成3项指定的课题课上表现（10%）15No1图数据库课程引论部分共30页，您现在浏览的是第15页!课程目标掌握图数据库的几种基本的查询算法和挖掘算法了解图数据库技术在不同领域的应用情况培养学生的独立思考和开展研究的能力。16No1图数据库课程引论部分共30页，您现在浏览的是第16页!GraphData17(a)ProteinNetwork(b)SocialNetworkNo1图数据库课程引论部分共30页，您现在浏览的是第17页!SomeChallengesinLargeGraphDataManagement18recursive

queriesNo1图数据库课程引论部分共30页，您现在浏览的是第18页!NetworkMotifs:SimpleBuildingBlocksofComplexNetworks(R.Milo,etal.@SCIENCE03)Networkmotifs

arepatterns(sub-graphs)thatrecurwithinanetworkmuchmoreoftenthanexpectedatrandom.

Networkmotifsalwayscorrespondtosomefunctionalpatternsindifferentnetworks.Questions:Howtofindsuchmotifsefficiently?Givenamotif,howtofindallembeddingsofthismotifefficiently?19No1图数据库课程引论部分共30页，您现在浏览的是第19页!SubgraphSearch20querygraphgraphdatabaseQuery:Whichpoundscontain“benzenering”?No1图数据库课程引论部分共30页，您现在浏览的是第20页!ShortestPathDistanceQuery21What’sthedistancebetweentwospecifiedindividuals?No1图数据库课程引论部分共30页，您现在浏览的是第21页!AnRDFDataExample–YagoProject22StructuralDataNo1图数据库课程引论部分共30页，您现在浏览的是第22页!AnRDFDataExample23No1图数据库课程引论部分共30页，您现在浏览的是第23页!AnRDFDataExample24No1图数据库课程引论部分共30页，您现在浏览的是第24页!SomeExistingGraphDatabaseSystemsThefollowingisalistofseveralwell-knowngraphdatabaseprojects:HyperGraphDB

-anopen-source(LPGL)graphdatabasesupportinggeneralized

hypergraphs

whereedgescanpointtootheredgesInfoGrid

-anopen-source/mercial(AGPLv3,freeforsmallentities)graphdatabasewithwebfrontendandconfigurablestorageengines(MySQL,PostgreSQL,Files,Hadoop)25No1图数据库课程引论部分共30页，您现在浏览的是第25页!AnExampleofNeo4jNeo4j/content/The_Matrix26Findingfriendsof“ThomasAnderson”and

thefriendsofthefriendstooNo1图数据库课程引论部分共30页，您现在浏览的是第26页!OutlineApplicationsandChallengesofGraphDataExitingGraphDatabaseSystemsAboutthecourse27No1图数据库课程引论部分共30页，您现在浏览的是第27页!课程网站网址：./course/Graphdb/index.html教材（作者、书名、出版社及出版年）：1.《数据挖掘概念与技术》JiaweiHan&MichelineKamber著，范明&孟小峰译，机械工业出版社（第二版）2.《MANAGINGANDMININGGRAPHDATA》，editedbyCHARUC.AGGARWAL,HAIXUNWANG,KluwerAcademicPublishers,20093.《语义网基础》GrigorisAntoniou;FrankvanHa