著者

井上 裕策 岩井原 瑞穂

出版者

九州大学

雑誌

九州大学大学院総合理工学研究科報告 (ISSN:03881717)

巻号頁・発行日

vol.17, no.3, pp.381-388, 1995

---

This paper proposes a method of representing relations implicitly using binary decision diagrams (BDD), which are data structures to represent logic functions compactly, and are widely used in computer-aided design (CAD)area We consider utilization of BDD for query processing in deductive databases. In this paper, we show two methods, called linear encoding and logarithmic encoding, to represent relations implicitly using BDDs. We compared the performances of these encodings with the traditional evaluation based on hash joins, and the proposed methods are faster than the hash-join-based methods over transitive closure queries on linear graphs and dense random graphs.