{"id":13006,"date":"2021-12-02T20:41:13","date_gmt":"2021-12-03T01:41:13","guid":{"rendered":"https:\/\/carleton.ca\/scs\/?page_id=13006"},"modified":"2026-06-02T14:59:25","modified_gmt":"2026-06-02T18:59:25","slug":"tr-99-05-the-case-for-the-rectangular-attribute-cardinality-map-in-query-optimization-modeling-prototype-validation-and-testing","status":"publish","type":"page","link":"https:\/\/carleton.ca\/scs\/research\/scs-technical-reports\/technical-reports-1999\/tr-99-05-the-case-for-the-rectangular-attribute-cardinality-map-in-query-optimization-modeling-prototype-validation-and-testing\/","title":{"rendered":"TR-99-05: The Case for the Rectangular Attribute Cardinality Map in Query Optimization: Modeling, Prototype Validation and Testing*"},"content":{"rendered":"\n
\n
\n\n
\n
\n
\n

\n TR-99-05: The Case for the Rectangular Attribute Cardinality Map in Query Optimization: Modeling, Prototype Validation and Testing*\n <\/h1>\n \n \n <\/header>\n\n <\/div>\n\n <\/div>\n\n <\/div>\n<\/section>\n\n

Carleton University
\nTechnical Report<\/a> TR-99-05
\nFebruary 1999<\/p>\n\n\n\n

The Case for the Rectangular Attribute Cardinality Map in Query Optimization: Modeling, Prototype Validation and Testing*<\/h2>\n\n\n\n
\n
\n
\n
\n
\n
\n
\n
\n
Murali Thiyagarajah & B. John Oommen<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n
\n

Abstract<\/h3>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n<\/div>\n\n\n\n

Current business database systems utilize histograms to approximate frequency dis\u00adtributions of attribute values of relations. These are used to efficiently estimate query result sizes and access plan costs and thus minimize the query response time for busi\u00adness (and non-commercial) database systems. In a recent work [12] we proposed a new form of histogram-like technique called the Rectangular Attribute Cardinality Map (R\u00adACM) that gives much smaller estimation errors than the traditional equi-width and equi-depth histograms currently being used by many commercial database systems. We also provided a fairly extensive mathematical analysis for its average and worst case errors for its frequency estimates which was verified for synthetic data.
\nThis paper demonstrates the earlier claim that the R-ACM is indeed a viable tool for query optimization. It, first of all, presents the R-ACM model and reports a prototype validation for the R-ACM for query optimization in real-world database systems. By investigating the performance of the scheme on an extensive set of experiments using real-life data [l, 2), we demonstrate that the R-AC!\\I scheme is much more accurate than the traditional histograms for query result size estimation. We anticipate that, due to its high accuracy and low construction costs, it could become an invaluable tool for query optimization in the future database systems.<\/p>\n\n\n\n

TR-99-05.pdf<\/a><\/p>\n","protected":false},"excerpt":{"rendered":"

Carleton University Technical Report TR-99-05 February 1999 The Case for the Rectangular Attribute Cardinality Map in Query Optimization: Modeling, Prototype Validation and Testing* Murali Thiyagarajah & B. John Oommen Abstract Current business database systems utilize histograms to approximate frequency dis\u00adtributions of attribute values of relations. These are used to efficiently estimate query result sizes and […]<\/p>\n","protected":false},"author":2,"featured_media":0,"parent":12244,"menu_order":0,"comment_status":"closed","ping_status":"closed","template":"","meta":{"_acf_changed":false,"_cu_dining_location_slug":"","footnotes":"","_links_to":"","_links_to_target":""},"cu_page_type":[],"class_list":["post-13006","page","type-page","status-publish","hentry"],"acf":{"cu_post_thumbnail":false},"_links":{"self":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13006","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages"}],"about":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/types\/page"}],"author":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/comments?post=13006"}],"version-history":[{"count":1,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13006\/revisions"}],"predecessor-version":[{"id":13007,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/13006\/revisions\/13007"}],"up":[{"embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/pages\/12244"}],"wp:attachment":[{"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/media?parent=13006"}],"wp:term":[{"taxonomy":"cu_page_type","embeddable":true,"href":"https:\/\/carleton.ca\/scs\/wp-json\/wp\/v2\/cu_page_type?post=13006"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}