Although a matrix of nodes is an option, it is much simpler to use a multipart rectangle (See Section 48.6 Shapes with Multiple Text Parts of the pgf manual):
\documentclass{scrartcl} % KOMA script (my preference)
\usepackage{graphicx}
\usepackage{subfig}
%\usepackage{tikz-rdf}
\usepackage{tikz}
\usepackage{tkz-graph}
\usepackage{tkz-berge}
\usetikzlibrary{matrix,arrows,positioning}
\usetikzlibrary{shapes,shapes.callouts,,decorations.text,shapes.misc,decorations.pathmorphing,shapes.geometric,backgrounds,fit,positioning,arrows}
\begin{document}
\begin{figure*}[ht!]%
\vspace{-0.2in}
% \centering
% \subfigure[b][{ Transaction Database $D$}]{%
% \includegraphics[scale=0.50]{newpics/DB.pdf}
\subfloat[\scriptsize Transaction Database $D$]{
\begin{minipage}[c]{0.3\textwidth}
\centering
\scalebox{.7}{
\begin{tabular}{| p{1cm} | p{1.5cm} | p{4cm} |}\hline
Vertex ID & Entity \mbox{vertex} & Adjacent Attribute Properties \\ \hline \hline
001 & Person1 & salary, gender, title \\ \hline
002 & Person2 & salary, gender, title, nationality \\ \hline
003 & Person3 & salary, gender, title \\ \hline
004 & Person4 & salary, gender, title, nationality \\ \hline
005 & Person5 & salary, gender, nationality \\ \hline
006 & Person6 & salary, title, nationality \\ \hline
007 & Paper1 & year, inProceedings, paperTitle \\ \hline
008 & Paper2 & year, inProceedings, paperTitle \\ \hline
009 & Paper3 & year, inProceedings, paperTitle \\ \hline
010 & School1 & locatedIn, name \\ \hline
011 & School2 & locatedIn, name \\ \hline
012 & School3 & locatedIn, name \\ \hline
\end{tabular}
}
\end{minipage}
\label{fig:db}%
}%
%
% \subfigure[b][{T-Index}]{%
% \includegraphics[scale=0.4]{newpics/FPtree.pdf}
\subfloat[\scriptsize T-Index]{
\begin{minipage}[c]{0.7\textwidth}
\centering
\scalebox{.5}{
\begin{tikzpicture}[node distance=1.5cm, every edge/.style={link}]
%
%Inserting nodes N1-N3
%
\node[circle,draw] (n0){$N_{0}$};
\node[circle,draw] (n1)[below left=of n0]{$N_{1}$};
\node[circle,draw] (n2)[below left=of n1]{$N_{2}$};
\node[circle,draw] (n3)[below left=of n2]{$N_{3}$};
\node[circle,draw] (n4)[below left=of n3]{$N_{4}$};
\node[circle,draw] (n5)[below right=of n2]{$N_{5}$};
\node[circle,draw] (n8)[below right=of n0]{$N_{8}$};
\node[circle,draw] (n11)[below right=of n0,xshift=1.5cm]{$N_{11}$};
\node[circle,draw] (n6)[below right=of n1]{$N_{6}$};
\node[circle,draw] (n7)[below right=of n6]{$N_{7}$};
\node[circle,draw] (n9)[below right=of n8]{$N_{9}$};
\node[circle,draw] (n10)[below =of n9]{$N_{10}$};
\node[circle,draw] (n12)[below right=of n11]{$N_{12}$};
%
%Inserting edges
%
\draw[-] (n0) -- (n1);
\draw[-] (n1) -- (n2);
\draw[-] (n2) -- (n3);
\draw[-] (n3) -- (n4);
\draw[-] (n2) -- (n5);
\draw[-] (n0) -- (n8);
\draw[-] (n0) -- (n11);
\draw[-] (n1) -- (n6);
\draw[-] (n6) -- (n7);
\draw[-] (n8) -- (n9);
\draw[-] (n9) -- (n10);
\draw[-] (n11) -- (n12);
%
%Inserting node labels
%
\node[rectangle] (root)[above left=of n0,xshift=1cm,yshift=-1.3cm]{root};
\node[rectangle] (salary)[above left=of n1,xshift=1cm,yshift=-1.3cm]{salary};
\node[rectangle] (gender)[above left=of n2,xshift=1cm,yshift=-1.3cm]{gender};
\node[rectangle] (title)[above left=of n3,xshift=1cm,yshift=-1.3cm]{title};
\node[rectangle] (nat)[above left=of n4,xshift=1cm,yshift=-1.3cm]{nationality};
\node[rectangle] (nat1)[below=of n5,yshift=1.3cm]{nationality};
\node[rectangle] (title2)[above left=of n6,xshift=1cm,yshift=-1.3cm]{title};
\node[rectangle] (nat2)[below=of n7,yshift=1.3cm]{nationality};
\node[rectangle] (year)[above left=of n8,xshift=1cm,yshift=-1.3cm]{year};
\node[rectangle] (inPr)[above left=of n9,xshift=1cm,yshift=-1.3cm]{inProceedings};
\node[rectangle] (papT)[below right=of n10,yshift=1.3cm,xshift=-1cm]{paperTitle};
\node[rectangle] (loc)[above =of n11,yshift=-1.3cm]{locatedIn};
\node[rectangle] (name)[below=of n12,yshift=1.3cm]{name};
%
%Entering the L values
%
\node[rectangle] (n1b)[above left=of salary,xshift=2cm,yshift=-1.3cm]{\{001,002,003,004,005,006\}};
\node[rectangle] (n2b)[above left=of gender,xshift=2cm,yshift=-1.3cm]{\{001,002,003,004,005\}};
\node[rectangle] (n3b)[above left=of title,xshift=2cm,yshift=-1.3cm]{\{001,002,003,004\}};
\node[rectangle] (n4b)[above =of nat,yshift=-1.7cm]{\{002,004\}};
\node[rectangle] (n4b1)[below=of nat1,yshift=1.5cm]{\{005\}};
\node[rectangle] (n6b)[above left=of title2,xshift=1.5cm,yshift=-1.3cm]{\{006\}};
\node[rectangle] (n7b)[below=of nat2,yshift=1.5cm]{\{006\}};
\node[rectangle] (n8b)[above left=of year,xshift=1.5cm,yshift=-1.3cm]{\{007,008,009\}};
\node[rectangle] (n9b)[above left=of inPr,xshift=2.5cm,yshift=-1.3cm]{\{007,008,009\}};
\node[rectangle] (n10b)[below=of papT,yshift=1.5cm]{\{007,008,009\}};
\node[rectangle] (n11b)[above=of loc,yshift=-1.6cm]{\{010,011,012\}};
\node[rectangle] (n12b)[below=of name,yshift=1.5cm]{\{010,011,012\}};
%
%Node-node links
%
\draw[-,green!50!black] (n4) -- (n5);
\draw[-,green!50!black] (n5) -- (n7);
\draw[-,green!50!black] (n3) -- (n6);
\draw[-,green!50!black] (n4) -- (n7);
%
%M(N3)
%
\node (tbl) [above left=of n0,xshift=1cm]{
\begin{tabular}{| c | c | p{2cm} | c |} \hline
salary & gender & title & $L$ \\ \hline
\$100,000 & Male & Professor & \{002\} \\ \hline
\$50,000 & Male & Assistant Professor & \{001\} \\ \hline
\$40,000 & Male & Assistant Professor &\{003\} \\ \hline
\$50,000 & Female & Assistant Professor & \{004\} \\ \hline
\end{tabular}
};
%
%M(N4)
%
\node (tbl2) [below right=of n4,xshift=-1.5cm]{
\begin{tabular}{| c | c | c | p{2cm} | c |} \hline
salary & gender & title & nationality & $L$ \\ \hline
\$45,000 & Female & Assistant Professor & Canadian & \{004\} \\ \hline
\$100,000 & Male & Professor & American & \{002\} \\ \hline
\end{tabular}
};
\node(head1)[above=of tbl,,xshift=-2.7cm,yshift=-1.7cm] {\large{$M(N_{3})$}};
\node(head2)[above=of tbl2,,xshift=-4.3cm,yshift=-1.7cm] {\large{$M(N_{4})$}};
\draw[->] (n3) -- (tbl.south);
\draw[->] (n4) -- (tbl2.north);
% The Dimensions DL multipart rectangle
\scalebox{1.1}{
\node (dl) [right=of n11,xshift=2cm,rectangle split,
rectangle split parts=9, draw,align=center,anchor=center]
{salary\nodepart{two}gender\nodepart{three}title\nodepart{four}nationality
\nodepart{five}year\nodepart{six}inProceedings\nodepart{seven}paperTitle
\nodepart{eight}locatedIn\nodepart{nine}name
};
}
\node (dlhead) [above=of dl,xshift=0.7cm,yshift=-1.4cm,align=center,font=\large]
{Dimension\\List $DL$};
% connecting some elements od Dimensions DL to the tree:
\draw[->,shorten >= 8pt] (n0) -- (dl.text);
\draw[->,shorten >= 12pt] (n11) -- (dl.three);
\draw[->,shorten >= -18pt] (n12) -- (dl.nine west);
\end{tikzpicture}
}
\end{minipage}
\label{fig:fp}%
}%
% \vspace{-0.2in}
\caption{T-index}%
\vspace{-0.2in}
\label{fig:star}
\end{figure*}
\end{document}

The new problem mentioned in the edit to the original question comes from the use of \scalebox; remove this command and use, for example, the text=\Large option:
\documentclass{scrartcl} % KOMA script (my preference)
\usepackage{graphicx}
\usepackage{subfig}
%\usepackage{tikz-rdf}
\usepackage{tikz}
\usepackage{tkz-graph}
\usepackage{tkz-berge}
\usetikzlibrary{matrix,arrows,positioning}
\usetikzlibrary{shapes,shapes.callouts,,decorations.text,shapes.misc,decorations.pathmorphing,shapes.geometric,backgrounds,fit,positioning,arrows}
\begin{document}
\thispagestyle{empty}
\begin{figure*}[ht!]%
\begin{minipage}[c]{0.7\textwidth}
\centering
\scalebox{.5}{
\begin{tikzpicture}[node distance=1.5cm, every edge/.style={link}]
%
%Inserting nodes N1-N3
%
\node[circle,draw] (n0){$N_{0}$};
\node[circle,draw] (n1)[below left=of n0]{$N_{1}$};
\node[circle,draw] (n2)[below left=of n1]{$N_{2}$};
\node[circle,draw] (n3)[below left=of n2]{$N_{3}$};
\node[circle,draw] (n4)[below left=of n3]{$N_{4}$};
\node[circle,draw] (n5)[below right=of n2]{$N_{5}$};
\node[circle,draw] (n8)[below right=of n0]{$N_{8}$};
\node[circle,draw] (n11)[below right=of n0,xshift=1.5cm]{$N_{11}$};
\node[circle,draw] (n6)[below right=of n1]{$N_{6}$};
\node[circle,draw] (n7)[below right=of n6]{$N_{7}$};
\node[circle,draw] (n9)[below right=of n8]{$N_{9}$};
\node[circle,draw] (n10)[below =of n9]{$N_{10}$};
\node[circle,draw] (n12)[below right=of n11]{$N_{12}$};
%
%Inserting edges
%
\draw[-] (n0) -- (n1);
\draw[-] (n1) -- (n2);
\draw[-] (n2) -- (n3);
\draw[-] (n3) -- (n4);
\draw[-] (n2) -- (n5);
\draw[-] (n0) -- (n8);
\draw[-] (n0) -- (n11);
\draw[-] (n1) -- (n6);
\draw[-] (n6) -- (n7);
\draw[-] (n8) -- (n9);
\draw[-] (n9) -- (n10);
\draw[-] (n11) -- (n12);
%
%Inserting node labels
%
\node[rectangle] (root)[above left=of n0,xshift=1cm,yshift=-1.3cm]{root};
\node[rectangle] (salary)[above left=of n1,xshift=1cm,yshift=-1.3cm]{salary};
\node[rectangle] (gender)[above left=of n2,xshift=1cm,yshift=-1.3cm]{gender};
\node[rectangle] (title)[above left=of n3,xshift=1cm,yshift=-1.3cm]{title};
\node[rectangle] (nat)[above left=of n4,xshift=1cm,yshift=-1.3cm]{nationality};
\node[rectangle] (nat1)[below=of n5,yshift=1.3cm]{nationality};
\node[rectangle] (title2)[above left=of n6,xshift=1cm,yshift=-1.3cm]{title};
\node[rectangle] (nat2)[below=of n7,yshift=1.3cm]{nationality};
\node[rectangle] (year)[above left=of n8,xshift=1cm,yshift=-1.3cm]{year};
\node[rectangle] (inPr)[above left=of n9,xshift=1cm,yshift=-1.3cm]{inProceedings};
\node[rectangle] (papT)[below right=of n10,yshift=1.3cm,xshift=-1cm]{paperTitle};
\node[rectangle] (loc)[above =of n11,yshift=-1.3cm]{locatedIn};
\node[rectangle] (name)[below=of n12,yshift=1.3cm]{name};
%
%Dimension list and the links to T-tree
%
\node (dl) [right=of n11,xshift=2cm,yshift=-1.5cm,rectangle split,
rectangle split parts=9, draw,align=center,font=\Large]{%
salary\nodepart{two}gender\nodepart{three}title\nodepart{four}nationality
\nodepart{five}year\nodepart{six}inProceedings\nodepart{seven}paperTitle
\nodepart{eight}locatedIn\nodepart{nine}name
};
\node(dlhead)[above=of dl,yshift=-1.7cm] {\large{$\begin{array}{c} \textrm{Dimension}\\\textrm{List }DL\end{array}$}};
\draw[->,dashed,red] (dl.text west) to [out=170, in= 90] (n1);%from salary
\draw[->,dashed,red] (dl.two west) to [out=170, in= 90] (n2); %from gender
\draw[->,dashed,red] (dl.three west) to [bend right] (n3); %from title
\draw[->,dashed,red] (dl.four west) to [bend right] (n4.15); %from nationality
\draw[->,dashed,red] (dl.five west) to [bend right] (n8); %from year
\draw[->,dashed,red] (dl.six west) to [bend right] (n9); %from inProceedings
\draw[->,dashed,red] (dl.seven west) to (n10); %from paperTItle
\draw[->,dashed,red] (dl.eight west) to (n11); %from locatedIn
\draw[->,dashed,red] (dl.nine west) -- (n12); %from name
\end{tikzpicture}
}
\end{minipage}
\caption{T-index}%
\vspace{-0.2in}
\label{fig:star}
\end{figure*}
\end{document}
