No1圖數(shù)據(jù)庫課程引論部分

Instructor:ZOU’leizoulei@北京大學計算機科學技術研究所InstituteofComputerScienceandTechnologyofPekingUniversityGraphDataManagement1No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第1頁!OutlineApplicationsandChallengesofGraphDataExitingGraphDatabaseSystemsAboutthecourse2No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第2頁!OutlineApplicationsandChallengesofGraphDataManagementExitingGraphDatabaseSystemsAboutthecourse3No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第3頁!SomeChallengesinLargeGraphDataManagementAnExample：ConsideringaSNSwebsite,therearemorethan1billionactiveusers.Query:Iwanttoknowwhether“TomisafriendofJack,orafriendofhisfriends…?”PossibleSolutions:(Storage)Storetheconnectionsbetweenindividualsinarelationaltable(Query)PerformSelf-joinRecursively….4No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第4頁!NetworkMotifs:SimpleBuildingBlocksofComplexNetworks(R.Milo,etal.@SCIENCE03)5No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第5頁!10December20226FrequentSubgraphPatternMining(A)(B)(C)GraphDatasetFrequentPatterns(minsupportis2)(1)(2)No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第6頁!7ReachablilityQuery123467859131011121415?Query(1,11)

Yes?Query(3,9)

NoNo1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第7頁!RDFDataManagementThe

ResourceDescriptionFramework(RDF)

isafamilyof

WorldWideWebConsortium

(W3C)

specificationsoriginallydesignedasa

metadata

datamodel.8WWWWebofPagesSemanticWebWebofDataNo1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第8頁!AnRDFDataExample9No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第9頁!SPARQLQueryQuery:FindallindividualswhowerebornonFeb.12,1809anddiedonApril.15,1865.SPARQLSyntaxSelect?nameWhere{?m<hasName>?name.?m<BornOnDate>“1809-02-12”.?m<DiedOnDate>“1865-04-15”.}QueryGraph10No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第10頁!OutlineApplicationsandChallengesofGraphDataExitingGraphDatabaseSystemsAboutthecourse11No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第11頁!SomeExistingGraphDatabaseSystemsNeo4j

-anopen-source/mercial(AGPLv3)graphdatabaseDEX

-Ahigh-performancegraphdatabaseandsoon…InternationalGraphDatabaseWorkshops:

./IWGD2010/index.html..au/~gdm2011/12No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第12頁!Neo4jAPIAnExampleprivate

void

printFriends(Nodeperson){

Traversertraverser=person.traverse(

Order.BREADTH_FIRST,//Traverse圖的模式

StopEvaluator.END_OF_GRAPH,//Traverse圖的停止條件

ReturnableEvaluator.ALL_BUT_START_NODE,//哪些圖節(jié)點被返回

MyRelationshipTypes.KNOWS,//按照那些邊來進行Traverse

Direction.OUTGOING);//Traverse的方向

for

(Nodefriend

:traverser)

{

System.out.println(friend.getProperty(

"name"

));

}}13No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第13頁!CourseContentGraphMining-frequentsubgraphminingIndexing&QueryProcessing-reachablilityquery-shortestpathquery-subgraphquery

-keywordsearchRDFDataManagement-Indexing&SPARQLQueryProcessing

14No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第14頁!課程考核課堂報告（30%）

每位學生報告一篇數(shù)據(jù)庫領域(含數(shù)據(jù)挖掘，信息檢索相關領域)頂級論文

（20分鐘+5分鐘提問）作業(yè)（30%）3項作業(yè)，完成3項指定的課題課上表現(xiàn)（10%）15No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第15頁!課程目標掌握圖數(shù)據(jù)庫的幾種基本的查詢算法和挖掘算法了解圖數(shù)據(jù)庫技術在不同領域的應用情況培養(yǎng)學生的獨立思考和開展研究的能力。16No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第16頁!GraphData17(a)ProteinNetwork(b)SocialNetworkNo1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第17頁!SomeChallengesinLargeGraphDataManagement18recursive

queriesNo1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第18頁!NetworkMotifs:SimpleBuildingBlocksofComplexNetworks(R.Milo,etal.@SCIENCE03)Networkmotifs

arepatterns(sub-graphs)thatrecurwithinanetworkmuchmoreoftenthanexpectedatrandom.

Networkmotifsalwayscorrespondtosomefunctionalpatternsindifferentnetworks.Questions:Howtofindsuchmotifsefficiently?Givenamotif,howtofindallembeddingsofthismotifefficiently?19No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第19頁!SubgraphSearch20querygraphgraphdatabaseQuery:Whichpoundscontain“benzenering”?No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第20頁!ShortestPathDistanceQuery21What’sthedistancebetweentwospecifiedindividuals?No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第21頁!AnRDFDataExample–YagoProject22StructuralDataNo1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第22頁!AnRDFDataExample23No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第23頁!AnRDFDataExample24No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第24頁!SomeExistingGraphDatabaseSystemsThefollowingisalistofseveralwell-knowngraphdatabaseprojects:HyperGraphDB

-anopen-source(LPGL)graphdatabasesupportinggeneralized

hypergraphs

whereedgescanpointtootheredgesInfoGrid

-anopen-source/mercial(AGPLv3,freeforsmallentities)graphdatabasewithwebfrontendandconfigurablestorageengines(MySQL,PostgreSQL,Files,Hadoop)25No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第25頁!AnExampleofNeo4jNeo4j/content/The_Matrix26Findingfriendsof“ThomasAnderson”and

thefriendsofthefriendstooNo1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第26頁!OutlineApplicationsandChallengesofGraphDataExitingGraphDatabaseSystemsAboutthecourse27No1圖數(shù)據(jù)庫課程引論部分共30頁，您現(xiàn)在瀏覽的是第27頁!課程網(wǎng)站網(wǎng)址：./course/Graphdb/index.html教材（作者、書名、出版社及出版年）：1.《數(shù)據(jù)挖掘概念與技術》JiaweiHan&MichelineKamber著，范明&孟小峰譯，機械工業(yè)出版社（第二版）2.《MANAGINGANDMININGGRAPHDATA》，editedbyCHARUC.AGGARWAL,HAIXUNWANG,KluwerAcademicPublishers,20093.《語義網(wǎng)基礎》GrigorisAntoniou;FrankvanHa