TAILIEUCHUNG - Keyword Search in Databases- P19

Keyword Search in Databases- P19:Conceptually, a database can be viewed as a data graph GD(V ,E), where V represents a set of objects, and E represents a set of connections between objects. In this book, we concentrate on two kinds of databases, a relational database (RDB) and an XML database. In an RDB, an object is a tuple that consists of many attribute values where some attribute values are strings or full-text; there is a connection between two objects if there exists at least one reference from one to the other | . SLCA-BASED SEMANTICS 89 PROPERTIES OF LCA AND SLCA Property Given a set S and two nodes v and Vj with v Vj then closest vi S closest vj S . Proof. We prove it by contradiction by assuming that closest vi S closest vj S . Then closest vi S rm vi S and closest vj S lm vj S rm vi S lm vj S . Recall that closest v S is chosen from lm v S and rm v S and lm vi S lm vj S and rm vi S rm vj S if all exists. If lm vj S rm vi S then lm vj S lm vi S therefore lm vi S lm vj S by the fact that lm vi S lm vj S . Similarly we can get that rm vi S rm vj S . Also we can learn that lm vi S rm vi S otherwise closest vi S lm vi S . Let lm denote lm vi S and rm denote rm vi S . It holds that lm vi vj rm. According to Property lca lm vj lca lm vi and lca rm vi lca rm vj . According to the definition of closest lca lm vi x lca rm vi and lca rm vj lca lm vj which is a contradiction. Property Let V and U be lists of nodes . V Vi vi and U ui ui such that V U . v Ui for 1 i l. Let lca V and lca U be the LCA of nodes in V and U respectively. Then 1. if lca V lca U then lca U lca V 2. if lca V lca U then either lca V x lca U or lca V f lca U then for any W with U W lca V f lca W . Proof. This is an extension of Property to more than two nodes. The proof is by induction when V and U contain only two nodes it is proven in Property . Assume that it is true for V U and W we prove it is true for V U W where V V U vi U U U ui with Vl ui. One important property of lca is that lca V lca lca V Vl . If lca U lca V then either lca U lca V or lca V lca U . Otherwise lca V lca U according to Property there are three cases of lca V and lca U and we only need to prove the last case . the case that lca V f lca U . Then for any W W U wi if lca U lca W then we are done otherwise lca W lca U then lca V f lca W because lca W lca W . 90 4. KEYWORD SEARCH IN XML DATABASES Tai ble id ki k2 kl idm id2 idi Figure Stack Data Structure EFFICIENT ALGORITHMS FOR .

TỪ KHÓA LIÊN QUAN
Đã phát hiện trình chặn quảng cáo AdBlock
Trang web này phụ thuộc vào doanh thu từ số lần hiển thị quảng cáo để tồn tại. Vui lòng tắt trình chặn quảng cáo của bạn hoặc tạm dừng tính năng chặn quảng cáo cho trang web này.