Một số cải tiến đối với phép biến đổi ma tập để tối ưu hóa câu truy vấn trên chương trình datalog

Bài báo tập trung thảo luận một số vấn đề liên quan đến phép biến đổi ma tập và đề xuất một số cải tiến nhằm nâng cao hiệu quả của nó trong việc tối ưu câu truy vấn trên chương trình Datalog. Mời các bạn cùng tham khảo nội dung chi tiết.
Nội dung trích xuất từ tài liệu:
Một số cải tiến đối với phép biến đổi ma tập để tối ưu hóa câu truy vấn trên chương trình datalogTẠPCHÍKHOAHỌC,ĐạihọcHuế,Số14,2002 MỘTSỐCẢITIẾNĐỐIVỚIPHÉPBIẾNĐỔIMATẬP ĐỂTỐIƯUHÓACÂUTRUYVẤNTRÊNCHƯƠNGTRÌNHDATALOG LêMạnhThạnh,TrươngCôngTuấn TrườngĐạihọcKhoahọc,ĐạihọcHuế 1.MỞĐẦU Phépbiếnđổimatậpđượcđánhgiálàmộttrongnhữngkỹ thuậttối ưucâutruyvấnrấtcóhiệuquả trongcơsởdữliệusuydiễn.Lýdoquantrọngđốivớisựthànhcôngcủakỹ thuậtnàylàsự kếthợpđượccác ưuđiểmcủakỹ thuật ước lượngtrênxuống(topdown)vàdướilên(bottomup),từđógiảmthiểuđượcsố cácsự kiệncầntínhvàtìmkiếmtrêncơ sởdữliệu.Tínhlôicuốncủakỹthuậtmatập đượcthể hiện ở tínhhiệuquả củanó([3,4,5]).Tuynhiên,phépbiếnđổimatập chưahẳnlàmộtchiếnlượcđịnhgiácâutruyvấntốtnhất.Bàibáotậptrungthảoluậnmộtsốvấnđềliênquanđếnphépbiếnđổimatậpvàđề xuấtmộtsốcảitiếnnhằmnângcaohiệuquả củanótrongviệctối ưucâutruyvấntrênchươngtrìnhDatalog. 2.MỘTSỐKHÁINIỆMCƠSỞ Trongkhuônkhổmộtbàibáo,chúngtôichỉtrìnhbàytómtắtmộtsốkháiniệmcơsởcủaphépbiếnđổimatập.Đểcócácchitiếtđầyđủhơncũngnhưmộtsốkháiniệmkháccủacơsởdữliệusuydiễncóthểxemtrong[1,5]. 2.1Tôđiểm(Adornment): Tôđiểmlàcáchchúthíchtrêncácvị từ để cungcấpthôngtinvề cácvị từ sẽđượcsử dụngnhưthế nàotrongquátrìnhđịnhgiácâutruyvấn.Tacómộtsố địnhnghĩa: (i)Mộtđốicủamộtđíchcontrongquytắcrđượcgọilàbuộcnếutrongsuốtquátrìnhđịnhgiácâutruyvấn,mọiđíchđượctạoratừđíchconnàycógiátrịhằngởvịtrícủađốinày.Ngượclại,đốiđượcgọilàtựdo. 5 (ii)Mộttôđiểmcủavịtừp(t1,t2,...,tk)làmộtdãycáckýtựbvàfcóchiềudàik.Nếukýhiệuthứicủatôđiểmlàbthìđốithứ icủaplàbuộc,nếukýhiệuthứicủatôđiểmlàfthìđốithứicủaplàtựdo.ChỉcócácvịtừIDBlàđượctôđiểm. (iii)Choquytắcp q1 q2 ... qnvàwlàtôđiểmcủavịtừp,tôđiểm icủacácđíchcon qi (t i ,1 ,..., ti ,ni ) đượcxácđịnhnhưsau:Nếuti,jlàhằnghoặcbiếnđãxuấthiệntrongđíchconqktrướcđó(k