Drug discovery strategies based on natural products are re-emerging as a promising approach. Due to its multi-target therapeutic properties, natural compounds in herbs produce greater levels of efficacy with fewer adverse effects and toxicity than monotherapies using synthetic compounds. However, the study of these medicinal herbs featuring multi-components and multi-targets requires an understanding of complex relationships, which is one of the fundamental goals in the discovery of drugs using natural products. Relational database systems such as the MySQL and Oracle store data in multiple tables, which are less efficient when data such as the one from natural compounds contain many relationships requiring several joins of large tables. Recently, there has been a noticeable shift in paradigm to NoSQL databases, especially graph databases, which was developed to natively represent complex high throughput dynamic relations. In this paper, we demonstrate the feasibility of using a graph-based database to capture the dynamic biological relationships of natural plant products by comparing the performance of MySQL and one of the most widely used NoSQL graph databases called Neo4j. Using this approach we have developed a graph database HerbMicrobeDB (HbMDB), and integrated herbal drug information, herb-targets, metabolic pathways, gut-microbial interactions and bacterial-genome information, from several existing resources. This NoSQL database contains 1,975,863 nodes, 3,548,314 properties and 2,511,747 edges. While probing the database and testing complex query execution performance of MySQL versus Neo4j, the latter outperformed MySQL and exhibited a very fast response for complex queries, whereas MySQL displayed latent or unfinished responses for complex queries with multiple-join statements. We discuss information convergence of pharmacochemistry, bioactivities, drug targets, and interaction networks for 24 culinary herbs and human gut microbiome. It is seen that all the herbs studied contain compounds capable of targeting a minimum of 55 enzymes and a maximum of 250 enzymes involved in biochemical pathways important in disease pathology.