数据库研究方法和论文写作 陆嘉恒 中国人民大学

报告大纲 数据库的研究主题选择 研究的动机和方法 论文写作方法

Topic + 数据库的研究： 数据+查询

查询种类： 数据种类： SQL 语言 关系数据 XQuery, XPath XML数据 SPARQL 流数据 Top -k 查询 网页数据 Topic 查询种类： SQL 语言 XQuery, XPath SPARQL Top -k 查询 Skyline查询 Keyword查询 近似 查询 图查询 …… 数据种类： 关系数据 XML数据 流数据 网页数据 概率数据 RDF数据 文本数据 图数据 ……

Topic 研究方向的选择： 知识积累 个人兴趣 导师推荐 导师推荐论文和书刊以及书刊 领域内的参考文献 了解该主题中的主要概念和理论

研究方向的选择： topic相关的leading experts 在做什么？从他们的文章中了解当前可做的问题 老问题的新发展：比如云计算和大数据等新内容与老问题之间的交叉等等 讨论 对于一个Problem而言，适宜将一个小的问题发掘透彻，而不是左顾右盼将小问题忽略

报告大纲 数据库的研究主题选择 研究的动机和方法 论文写作方法

三句格言（1） 科学上没有平坦的大道，真理长河中有无数礁石险滩。只有不畏攀登的采药者，只有不怕巨浪的弄潮儿，才能登上高峰采得仙草，深入水底觅得骊珠。

三句格言（2） 当官的道路红彤彤 经商的道路黄灿灿 学术的道路黑洞洞

三句格言（3） 不要努力成为一个成功者，要努力成为一个有价值的人。 

有了好的idea就完成了学术论文的一半！ New Idea 新的想法的确立是十分不易的，是一个学术研究的关键，这是一个不断思索的过程。 对于一个Problem： 解决方法是什么？ idea是否是新的？ 是否有道理？ 是否可行？ 否有更好的idea？ 有了好的idea就完成了学术论文的一半！

一个idea需要有理论分析和实验验证： 理论分析需要较好的数学功底 实验验证需要较好的实验设计能力 理论分析要周全，最好有严格的数学证明 New Idea 一个idea需要有理论分析和实验验证： 理论分析需要较好的数学功底 实验验证需要较好的实验设计能力 理论分析要周全，最好有严格的数学证明 实验验证尽量使用基准测试方案或其他学者常使用的数据 实验要有合理的对比 保证实验的可重复性 Tips

思：边读论文边思考，构建知识体系，思考解决新问题的思路； 学：学习一个领域的相关知识，以及理论分析手段和实验实现方法 Summary 研究是学、思、做、写四个方面的结合。 思：边读论文边思考，构建知识体系，思考解决新问题的思路； 学：学习一个领域的相关知识，以及理论分析手段和实验实现方法 做：研究需要实验来检验自己的假设和细节，发现许多在分析阶段看不到的东西 写：论文的写作是一个科学工作者不可缺少的方面，研究成果要通过论文分享和被同行认可

计算机科学界非常重视会议论文，高档次的会议论文体现了国际一流的学术水平，在数据库领域一流的会议和刊物有： Paper 计算机科学界非常重视会议论文，高档次的会议论文体现了国际一流的学术水平，在数据库领域一流的会议和刊物有： 会议： SIGMOD (ACM Conference on Management of Data) PODS (ACM SIGMOD Conference on Principles of DB Systems) ICDE (IEEE International Conference on Data Engineering) PVLDB (International Conference on Very Large Data Bases) 刊物： TODS (ACM Transactions on Database Systems) TOIS (ACM Transactions on Information and Systems) IEEE TKDE (IEEE Transactions on Knowledge and Data Engineering) VLDBJ (VLDB Journal)

-Support（theoretical or experimental） -Conclusion -Reference Paper Structure 论文的八大结构： -Title -Abstract -Introduction -Previous work -Our work -Support（theoretical or experimental） -Conclusion -Reference

**关键要有吸引力** Title: 论文的题目要能够清楚地表达主要的工作，字数不能过长 Abstract： 目的：总结自己的工作 内容： 研究的问题 自己的方法 自己的方法的特点和优点 方法的结果 Attractive

Introduction 目的：介绍文章的背景和组织结构 内容：问题P十分的重要，A、B和C都已经做过了XX工作，他们的工作取得了哪些成绩，但是都存在某些缺点，我们提出了方法D,阐述D的特点和优点，以及D的实验结果，最后介绍文章的组织结构。 Tips 对别人的工作不能有太多批评，否则显的很不客观，容易降低文章的质量。

对每项重要的历史工作进行简短的回顾(一到几句)，注意要回顾正确，抓住要点，避免歧义 和自己提出的工作进行比较 Related work 目的：说明自己与前人的不同 内容： 将历史上前人的工作分成类别 对每项重要的历史工作进行简短的回顾(一到几句)，注意要回顾正确，抓住要点，避免歧义 和自己提出的工作进行比较 不要忽略前人的重要工作，要公正评价前人的工作，不要过于苛刻 强调自己的工作和前人工作的不同，最好举出各自适用例子

复杂的冗长的证明和细节可以放在附录中，这里关键是把问题阐述清楚 特例和例外应该在脚注中给予说明 Our work 目的：描述自己的工作 内容： 从读者角度阐明定义和表示法 提供算法的伪码，图解和相应解释 用设问的方式回答读者可能提出的潜在问题 复杂的冗长的证明和细节可以放在附录中，这里关键是把问题阐述清楚 特例和例外应该在脚注中给予说明

通常，对自己观点的支撑和论证需要理论和实验两个方面的阐述 Support 通常，对自己观点的支撑和论证需要理论和实验两个方面的阐述 Theoretical analysis 目的：对自己的方法的理论支持 内容：理论阐述、证明等 Experiment 目的：通过实验来验证自己的工作 内容： 实验设计（保证其他读论文的人可以根据描述重复实验） 对比 结论（从试验中得出了什么结论）

Conclusion 目的：总结全文，结束文章 内容： 快速简短的总结 未来工作的展望 Reference 目的：对相关重要背景文献的引用 选择引文（众所周知的结论不必引用） 引文与文章保持一致

好文章一般的特点： 正确选题 合适的切入点 简洁明了 说清自己的贡献 可靠的/可重现的结果 可重复的过程 好的文章结构和逻辑流程 Rules 好文章一般的特点： 正确选题 合适的切入点 简洁明了 说清自己的贡献 可靠的/可重现的结果 可重复的过程 好的文章结构和逻辑流程 精选的参考文献

Title: Optimal Top-k Generation of Attribute Combinations SIGMOD 2012 Title: Optimal Top-k Generation of Attribute Combinations based on Ranked Lists 题目指出了文章提出了一个最优属性组合产生的方法

further develop optimizations for efficient query evaluation to SIGMOD 2012 研究的问题： In this work, we study a novel topk query type, called topkm queries. Suppose we are given a set of groups and each group contains a set of attributes, each of which is associated with a ranked list of tuples, with ID and score. This problem has a wide range of applications from databases to search engines on traditional and non-traditional types of data (relational data, XML, text, etc.). We show that a straightforward extension of an optimal top-$k$ algorithm, the Threshold Algorithm (TA), has shortcomings in solving the \topkm{} problem. To overcome this weakness, we provide here, for the first time, a \emph{provably instance-optimal} algorithm and further develop optimizations for efficient query evaluation to reduce computational and memory costs and the number of accesses. We demonstrate experimentally the scalability and efficiency of our algorithms over three real applications. 应用背景 我们方法的优点和结果

SIGMOD 2012 1. Introduction： ——1.1 问题的定义 ——1.2 应用 ——1.3 主要的学术贡献 2. PROBLEM FORMULATION 3 BACKGROUND AND RELATEDWORK

算法理论分析，关键所在 SIGMOD 2012 4 TOP-K,M ALGORITHMS 4.1 Access model: sorted and random accesses 4.2 Baseline algorithm: ETA 4.3 Top-k,m algorithm: ULA 4.4 Optimized top-k,m algorithm: ULA+ 4.5 Optimality properties

方法的应用和实验验证理论 论文的结论部分 SIGMOD 2012 5. XML KEYWORD REFINEMENT 6. EXPERIMENTAL STUDY 7. CONCLUSION AND FUTURE WORK 结论和将来的发展； 方法的应用和实验验证理论 论文的结论部分

有力的数学论证和公式推导往往是检验一篇论文质量高低的一个重要的因素。 Theoretical Computer Science 复杂度分析 树的性质 图论 递归的性质 级数运算 数论 概率公式 矩阵运算 微积分公式 求极限方法 …… 有力的数学论证和公式推导往往是检验一篇论文质量高低的一个重要的因素。

复杂度计算 f(n)的上界 f(n)的下界 f(n)的确定界 Eg：

常用分布 二项分布： 泊松分布： 正态（高斯）分布： 高斯分布曲线，多元高斯分布等等。

常用级数（用来公式推导、近似计算等） 泰勒级数的基本表示形式： 常用某公式在0处的展开式来作为推导：

图论中的概念和经典算法 图论中的基本表示方法：节点集、边集…… 图论中的经典算法： Dijkstra算法 Floyd算法 Kruskal算法 ……

除去以上的介绍外，常用的微积分的公式、线性代数的计算方法等需要熟练掌握。 总之，理论计算机的水平提高在于不断的积累和研究中的应用。

克服英语论文语言障碍 多读相关的论文进行学习和揣摩 Tips 准备一个笔记本，随时记录优秀的英语论文里的句子。

Abstract 部分的优秀句子举例（1） 开门见山，直接说本文的主要内容： We study the problem of processing subgraph queries on a database that consists of a set of graphs. The answer to a subgraph query is the set of graphs in the database that are supergraphs of the query. In this article, we propose an efficient index, FG*-index, to solve this problem. 说本文的主要内容和研究问题的重要性 This paper investigates the problem of efficiently computing the confidences of distinct tuples  in the answers to conjunctive queries with inequalities (<) on tuple-independent probabilistic databases. This problem is fundamental to probabilistic dabases and was recetly stated open. 经常说某些工作是第一个工作 This is the first work that reasons about keyword search strategies from a formal perspective. 说试验结果方面的改善 Our experimental results show that this reformulation of non-inner joins as complex predicates can improve optimization time by orders of magnitude, compared to known algorithms dealing with complex join predicates and non-inner joins. once again, this gives dynamic programming a distinct advantage over current memoization technqiues.

Abstract 部分的优秀句子举例（2） 说新方法的额外开销很小 We also show through complexity and performance analysis that the structural signature scheme is efficient; with respect to the Merkle hash signature, it incurs comparable cost for signing the trees and incurs lower cost for user-side integrity verification. 说已有的研究很多，但是还没有满足某个条件的： Nearest neighbour (NN) search in high dimensional space is an important problem in many applications. Ideally, a practical solution (i) should be implementable in a relational database, and (ii) its query cost should grow sub-linearly with the dataset size, regardless of the data and query distributions. Despite the bulk of NN literature, no solution fulfills both requirements, except local sensitive hashing (LSH). 说某个工作和前面的工作不一样，不要总是用“different from” This technique diverges from the research attempting the challenging problem to compress a single genome or recent research on compressing a large database of unrelated sequences. We do not consider the process of generating the variations, which can be a challenging problem itself, but assume that the variation data have been provided. . 说前人工作比较多，但是还是有一些缺点和值得改进的地方 Despite the significant amount of work on streaming XML processing, most of the work focused on XML filtering (such as XFilter) or single extraction node (not multiple extraction nodes). As a result, the work on efficient algorithms for tuple extraction is rather limited/ TurboXPath is the latest system specifically designed for tuple extraction.

总结 数据库的研究主题选择：老问题的新发展和结合 研究的动机：自己觉得研究内容有价值有创意最重要 英语论文写作关键在于揣摩和模仿

总结的格言 所有的方法都需要勤奋的练习

祝大家在数据库研究领域取得好成绩！