No.1+图数据库课程+引论部分.ppt

1、Instructor: ZOU lei ,北京大学计算机科学技术研究所 Institute of Computer Science and Technology of Peking University,Graph Data Management,1,Outline,Applications and Challenges of Graph Data Exiting Graph Database Systems About the course,2,Outline,Applications and Challenges of Graph Data Management Exiting Graph

2、 Database Systems About the course,3,Graph Data,4,(a) Protein Network,(b) Social Network,Some Challenges in Large Graph Data Management,An Example： Considering a SNS website, there are more than 1 billion active users. Query: I want to know whether “Tom is a friend of Jack, or a friend of his friend

3、s?” Possible Solutions: (Storage) Store the connections between individuals in a relational table (Query) Perform Self-join Recursively.,5,Some Challenges in Large Graph Data Management,6,recursivequeries,Network Motifs: Simple Building Blocks of Complex Networks (R. Milo, et al.SCIENCE03),7,Network

4、 Motifs: Simple Building Blocks of Complex Networks (R. Milo, et al.SCIENCE03),Network motifsare patterns (sub-graphs) that recur within a network much more often than expected at random. Network motifs always correspond to some functional patterns in different networks. Questions: How to find such

5、motifs efficiently ? Given a motif, how to find all embeddings of this motif efficiently?,8,August 5, 2020,9,Frequent Subgraph Pattern Mining,(A),(B),(C),Graph Dataset,Frequent Patterns (min support is 2),(1),(2),Subgraph Search,10,Query: Which compounds contain “benzene ring” ?,11,Reachablility Que

6、ry,1,2,3,4,6,7,8,5,9,13,10,11,12,14,15,?Query(1,11) Yes ?Query(3,9) No,Shortest Path Distance Query,12,Whats the distance between two specified individuals ?,RDF Data Management,TheResource Description Framework (RDF)is a family ofWorld Wide Web Consortium(W3C)specifications originally designed as a

7、metadatadata model.,13,WWW Web of Pages Semantic Web Web of Data,An RDF Data Example Yago Project,14,Structural Data,An RDF Data Example,15,An RDF Data Example,16,SPARQL Query,Query: Find all individuals who were born on Feb. 12, 1809 and died on April. 15, 1865. SPARQL Syntax Select ?name Where ?m

8、?name. ?m “1809-02-12”. ?m “1865-04-15”. Query Graph,17,An RDF Data Example,18,Outline,Applications and Challenges of Graph Data Exiting Graph Database Systems About the course,19,Some Existing Graph Database Systems,The following is a list of several well-known graph database projects: HyperGraphDB

9、- an open-source (LPGL) graph database supporting generalizedhypergraphswhere edges can point to other edges InfoGrid- an open-source / commercial (AGPLv3, free for small entities)graph database with web front end and configurable storage engines (MySQL, PostgreSQL, Files, Hadoop),20,Some Existing G

10、raph Database Systems,Neo4j- an open-source / commercial (AGPLv3)graph database DEX- A high-performance graph database and so on International Graph Database Workshops: .au/gdm2011/,21,An Example of Neo4j,Neo4j /content/The_Matrix,22,Finding friends of “Thom

11、as Anderson” and the friends of the friends too,Neo4j API-An Example,privatevoidprintFriends( Node person ) Traverser traverser = person.traverse( Order.BREADTH_FIRST, /Traverse图的模式 StopEvaluator.END_OF_GRAPH, / Traverse图的停止条件 ReturnableEvaluator.ALL_BUT_START_NODE, / 哪些图节点被返回 MyRelationshipTypes.KN

12、OWS, /按照那些边来进行Traverse Direction.OUTGOING ); / Traverse的方向 for( Node friend: traverser ) System.out.println( friend.getProperty(name) ); ,23,Outline,Applications and Challenges of Graph Data Exiting Graph Database Systems About the course,24,Course Content,Graph Mining - frequent subgraph mining Ind

13、exing & Query Processing - reachablility query - shortest path query - subgraph query - keyword search RDF Data Management - Indexing & SPARQL Query Processing,25,课程网站,网址： 教材（作者、书名、出版社及出版年）： 1. 数据挖掘概念与技术 Jiawei Han Frank van Harmelen 著, 机械工业出版社, 2008,26,课程考核,课堂报告 （30%） 每位学生报告一篇数据库领域(含数据挖掘，信息检索相关领域)顶级论文（20分钟+5分钟提问） 作业（30%） 3 项作业，完成3项指定的课题 课上表现（10%）,27,课