Thornton, Mitch

Committee Member

Harden, James

Committee Member

Reese, Robert

Date of Degree


Document Type

Graduate Thesis - Open Access

Degree Name

Master of Science


Technology is improving at an amazing pace and one reason for this advancement is because of unprecedented growth in the field of Information Technology and also in Digital Integrated Circuit technology over the past few decades. The size of a typical modern database is in the order of high ends of gigabytes and even terabytes. Researchers were successful in designing complex databases but there is still lot of activity on effectively making use of this stored information. There have been significant advancements in the field of "Logic optimization" and also in "Information storage and retrieval" but there has been very little transfer of these methods. The purpose of this study is to investigate the use of powerful Computer Aided Design (CAD) techniques for efficient information storage and retrieval. In the work presented in this thesis, it is shown that Decision Diagrams can be used for efficient data storage and information retrieval. An efficient technique is proposed for each of the two key areas of research in Database systems known as "Query Optimization" and "Datamining". Encouraging results are obtained indicating that using hardware techniques for information processing can be a new approach for solving these problems. An SQL query is represented using a hardware data structure known as an AND/OR graph and an SQL parser is interfaced with AND/OR package to achieve query optimization. Optimization using AND/OR graphs works only in the Boolean domain and to make the process of query optimization more complete it has to be investigated in Multivalued domain. The possibility of using MDD as a data structure to represent the query in the multi valued domain is discussed and a synthesis technique is developed to synthesize Multi Valued Logic Networks using MDD. Another useful data structure known as BDD can be used to store the large transaction files used in datamining applications very effectively.