  New applications of data mining, such as in biology, bioinformatics, or
sociology, are faced with large datasetsstructured as graphs. We introduce a
novel class of tree-shapedpatterns called tree queries, and present algorithms
for miningtree queries and tree-query associations in a large data graph. Novel
about our class of patterns is that they can containconstants, and can contain
existential nodes which are not counted when determining the number of
occurrences of the patternin the data graph. Our algorithms have a number of
provableoptimality properties, which are based on the theory of conjunctive
database queries. We propose a practical, database-oriented implementation in
SQL, and show that the approach works in practice through experiments on data
about food webs, protein interactions, and citation analysis.
