ѧ
JOURNAL OF SOFTWARE
1999 10 7ڡNo.7 Vol.10 1999



ýѯԼѯ
ƽܰӢʩ
ժҪо˶ýݿĲѯ,ṹĶýѯMOQL(multi-media object query language).ֻܹ֧͡ṹͬϵʱ̬ϵϢĶýѯ.DB2ݿΪ洢,һӺͱ任,ǿԽûMOQLѯ任Ϊʽ,дŻ,ѯʽתΪܹDB2ݿеDB2SQLC++ѯ.
ؼʡýݿ,ѯ,ѯŻ.
ͼšTP311
Multimedia Object Query Language and Its Query Processing
TIAN Zeng-ping DANG Hua-rui ZHOU Ao-ying SHI Bai-le
(Department of Computer Science Fudan University Shanghai 200433)
Abstract In this paper, the authors study the query requirements of multimedia database and propose a structured multimedia object query language (MOQL). The language can support queries based on type, structure, synchronous relations, temporal relations, and contents of multimedia data. Taking the DB2 relational database system as a storage mechanism, they define a set of algebraic operators and some transformation rules, by which the MOQL queries defined by the users can be transformed into a set of algebraic formula and optimized. Finally, the algebraic formula can be transformed into execution plan in DB2SQL and C++ procedures, which can be run on DB2 system.
Key wordsMultimedia database, query language, query optimization.
Դӡý塱,ýϢѯͳΪݿоҪ,ȡ˺ܶɹ.оĽչ,ýϢĲѯԼѯԵĹܽṹҲȷ.D.Woelk[1]C.Goble[2]ָ,ڽṹ͵ĲѯǶýϢѯҪ.T.D.Little[3]A.Karmouch [4]ýݿӦֻ֧ڶýݱֵʱͬϵĲѯ.ڽṹ͵Ķýѯʹöý֯ԪݿԱѯ,Ϊûṩ˸Ϣѯռ.
ýݿ⽫ͳݿֵĲѯϢϵͳݵĲѯ.E.Bertino˵MULTOS[5]ֶ֧ͼıĴѯ.M.Flicker[6]QBICϵͳܸͼ״ɫݽвѯ.A.Gupta[7]VIMSYSϵͳܸݸѯͼ.Wu[8]COREϵͳܹıƶȺģȵȲѯͼ.E.Oomoto[9]ƵOVIDϵͳܸݶ̬ƵӰвѯ.ݲѯʹôͳݿȷѯΪƻģѯ.
оǰ˹ʱע⵽,ĸֶýѯԶרŵӦ,ʹ÷Χխ,ҸԵ﷨ʽϤݿSQLϴ,ѧϰʹ,,ԵҲͬ.ͼӦΪ,о˶ýݿѯ,ṹĶýѯMOQL(multi-media object query language).ֻܹ֧͡ṹͬϵʱ̬ϵϢĶýѯ.DB2ݿΪ洢,һӺͱ任.ǿԽûMOQLѯ任Ϊʽ,дŻ,,ѯʽתΪܹDB2ݿеĲѯ.ĵĹǿйʷͼͼϵͳ.
ĵ1۶ýѯ.2ڽMOQLĶýģ.3ڸMOQLԵĶ.4۪MOQLԵĲѯŻ.5ܽȫĹ,Ҫһо.
1ýϢĲѯ
ڶýϢѯо,ϵͳĿӦ͵Ĳͬ,˸ֲͬ.˵,ýݿϵͳӦֻ֧͡ṹýݱֵͬϵýݼʱ̬ϢĲѯ.
(1) ͺͽṹĲѯ,֧ûնͺڲṹѯý.ڶýݿ,ý֯ͺͽṹϢûĵ,ԲѯýҪ.,ѯʷͼ͡ѯкʷͼǻͺͽṹĶýѯ.
(2) ͬϵĲѯԶýֵʱԻͬԱֵʱϵΪĲѯ.ýϢȡڸݵ,ȡЩݱֵʱϵ.,ֻ֧ͬϵĲѯǶýѯеҪ.,ѯڶ̬ƵӰĵƬϡȾͬϵѯ.
(3) ݵĲѯݷǽṹ,ͼ񡢶̬ƵӰıȵϢѯý.ͳݿѯڶֵνʲϵ׼ȷֵ.ڶýݿ,ûϣͼƵӰıȷǽṹϢвѯ.
(4) ʱ̬ϢĲѯܹĳЩʱѯý.оĶýݿڴ洢йʷͼĶýϢ,,ֻ֧ʱ̬ϢĲѯǱزٵĹ.
ýݿĲѯֶ,ӦõĳڲϷչͱ仯,,޷ȫоٵ.ĸͼӦõҪ,ǰ˵оɹ,4ҪҪ,ܹЩҪMOQL.
2ýģ
MOQLԻƵĶýģ,ģ;ص㣺
(1) ýϢݺΪģ.ý͡ԼκͷǶýģ͵Ҫ.һýɶʶ(OID)һԪֵͬԵʱȼһЧʷʱ.͡༰Ƕý֯.ͶһƽṹĶýĹṹ.һļ.֯ʽ,ϵͳеγһ޻ͼ.̳иĽṹΪͱ.˶ýΪ.ϵͳ֧෽,ƽ̨޹ط.һϵͳķ,κûԷĵöʹӦڷִ.ƽ̨޹صķҪǶýıֹ.κûԶýıҪ󶼵Ӧûִ.
(2) ýϢıģ.ģҪڱֵĿռʱԽģ.Ϊʵֱֵƽ̨޹,JavaԶýıֹ.JavaԶ󷽷,ʵֶ󷽷Ŀƽִ̨,ݿInternetϵµĳ.
(3) ڱֵĿռʱ佨ģ,Ҳĳ.ýֵĿռJavaԶıַ,ù̶ռ.ûþȫ㹦ܵJava(ĳForm)Ŷýıֿռ.ԶýֵʱԲǹ̷ʽģ.ý󴴽߲Ҫý,Ҫݱֵʱ˳ϵ.
3ýѯMOQL
3.1 3ݿʽ
MOQL֧3ݿʽ,OIDѯƲѯԼSELECTѯ.
(1) OIDѯ
ڶýݿϵͳ,ÿͶ塢ඨԼӶΪڲ.ÿڲһΨһOIDʶ.ûͨOIDֱӼҪѯĶϢ,,#130,#208.
(2) Ƽ
ڶýݿϵͳ,ʽظӡͻĶ,ȡֵ޹.һ1,,һֻܸһ.ûԸݶƻöйϢ.,M-QuanTuȫͼ,ûͿɻȫͼйϢ.
(3) SELECT
SELECT֧ûݡʱϢṹͬϵĶýѯ.,вѯҳֽкСʷƾáͼɫsampmapɫƶȴ0.7ʷͼ,Ҫǲж(animClassΪ),ֽͬʱʼ,ѯsampmapͼɫƶ,ӴСǰ5,дµMOQL䣺
SELECT m
FROM m IN mapClass
WHERE SUBSTRING (m.exptxt,ʷƾá) 
and Grade(m.map.color, sampmap.color)>0.7
WHEN INt(m,qingDynasty) 
STRUCT m CONTAINS {animClass} 
SYNCH m.exptxt STARTS m.expvoc
ORDER [5] ASC (Grade)
SELECT,FROM,WHERE,WHEN,STRUCT,SYNCHORDERΪ֣SUBSTRINGGradeΪûϵͳνʺͺINt,CONTAINSSTARTSΪڲν.
3.2 SELECT
SELECTûʶýݿҪʽ.ֻ֧ݡʱϢṹͬϵĲѯ,ʽ£
SELECT {·ʽ}
FROM IN
[WHERE ]
[WHENʱ]
[STRUCTṹ]
[SYNCHͬ]
[ORDER[ؽĿ]]
SELECT FROMӾ˵ѯĿ꼰Χ,WHERE,WHEN,STRUCTSYNCHֱ˵ѯӦʱṹͬ.
(1) SELECTFROMӾ
SELECTFROMӾ˵ѯĽѯΧ.ѯһ·ʽ.
1.·ʽ£
XΪTĶ,XΪ·ʽ,TΪ.
A0,A1,...,Ai(i0)Ϊ·ʽ,AiȡֵΪT,AT,A0,A1,A2,...,Ai.AΪ·ʽ,ΪA.
A0,A1,...,Ai(i0)Ϊ·ʽ,AiֵΪC,fCϵķ,fĲΪT1,...,Tn,a1,...,anֱǾT1,...,Tnֵ,A0,A1,...,Ai.f(a1,...,an)Ϊ·ʽ,fķֵΪ.
(2) WHEREORDERӾ
WHEREORDERӾ˵ѯĿӦԼظûĲѯĿ˳.
2. ʽ£
P1P2Ϊ·ʽ,op{>,<,,=,,}ΪһȽϷ,aΪ,P1(op)a,a(op)P1P1(op)P2Ϊʽ(aP1ͼ)
P1P2Ϊ·ʽ,aΪ,QΪûνʻϵͳν,Q(P1,a)Q(P1,P2)Ϊʽ.MOQL֧DB2SQLֵ֧ڲνʣ
C1C2Ϊʽ,C1 and C2 ,C1 or C2not C1Ϊʽ.
ORDERӾĽṹΪ
ORDER [k] ASCDESC (f1,f2,...,fn),У
. kΪظûĽĿ
. ASCDESCֱ˵f1,f2,...,fnֵ
. f1,f2,...,fnΪWHEREӾеģȻƶȺ.
ڲѯģ,صģԼԶΪӦϵķ,,̺·睊ʽ.
(3) WHENӾ
WHENӾ˵ûԲѯʱҪ.MOQL֧ʷʱϢĲѯ.Ϊ˱ͲʱϢ,ӣ
BeginOf(һԪ),EndOf(һԪ),Extend(Ԫ),SameTime(Ԫ).
ֱ۽£
. BeginOf(a)aĿʼ,,BeginOf(qingDynasty)=1618
. EndOf(a)aĽ
. a Extend babʱĲ
. a SameTime babʱĽ.
ʱ£
ٶʱ䳣,确Now,qingDynastyΪʱ
t1,t2Ϊʱ,f{BeginOf,EndOf},g{Extend,SameTime},f(t1),g(t1,t2)Ϊʱ.
MOQLṩ4Ԫʱν,BEFOREt,AFTERt,INt,OVERLAPt
.BEFOREt(a,b)aʱbʱ䣻
.AFTERt(a,b)aʱbʱ䣻
.OVERLAPt(a,b)aʱbʱص
.INt(a,b)aʱbʱ.
3. ʱʽ£
abΪʱP{BEFOREt,AFTERt,INt,OVERLAPt},P(a,b)Ϊʱʽ
SQΪʱʽ,S and Q,S or Qnot QΪʱʽ.
(4) STRUCTӾ
MOQLSTRUCTӾ˵ѯĿĽṹ.һṹνCONTAINSṹ.
4. ṹʽ£
PΪ·ʽ,T1,...,TnΪ,P CONTAINS{T1,T2,...,Tn}Ϊṹʽ
S1,S2Ϊṹʽ,S1 and S2,S1 or S2not S1Ϊṹʽ.
(5) SYNCHӾ
ݻʱ(TIB)ͬϵʾ,ýݱֵͬϵɱʾΪʱʱϵ.J.F.Allenָ[10],ʱ֮7ֲظϵ,ֱBEFORE,MEETS,OVERLAPS,DURING,STARTS,FINISHESEQUALS.MOQLֻ֧ЩͬϵĶýѯ.
5. ͬʽ£
P1P2Ϊ·ʽ,R{BEFORE,MEETS,OVERLAPS,DURING,STARTS,FINISHESEQUALS},P1(R)P2Ϊͬʽ
P1P2Ϊ·ʽ,NΪ,op{>,<,,=,,},Length(P1)(op)Length(P2), Length(P1)(op)NN(op)Length(P1)Ϊͬʽ
S1S2Ϊͬʽ,S1 and S2, S1 or S2not S1Ϊͬʽ.
,LengthΪϵͳ庯,ضýıʱ䳤(öڱֵжıʱ䳤).
4ѯ
MOQLѯϵͳDB2 V2Ϊ洢,ùϵ洢ṹ,ļƴ洢ǽṹĶ,ͼֺ,û庯UDFʵƻģȺ,ֻ֧ݵĶýѯ.MOQLΪԴ,DB2 SQLC++setΪݴȡĿ.ѯ7ɣ﷨顢任ѯд任Żɴȡִдȡ.
4.1 ﷨
﷨3ֹܣ(1) ûOIDĲѯ,ȡOIDϢɲѯṹ,OIDѯṹ͸OIDģḶ̌(2) ûڶƵĲѯ,ѯOID-ơձ,ȡOIDϢ,ɲѯṹ,OID͸̣(3) ûSELECTѯ,ûѯǷϺMOQL﷨.任SELECTѯӦMOQL﷨.
4.2 任
任Ĺ,ʹ·ʽƿʼ.
4.3 ѯд
ѯдɲѯṹ,SELECTѯĿдΪ·ʽĶ.
4.4 任
任дĲѯ任Ϊһʽ.еĶڱMOQLѯ,ױDB2 SQLʵ,ͳĹϵֲܳDB2 SQL,,Ƕһ,Ϊѯڲ.
.ͶӰPJ[A]PJ[A](R)=A(R)
.ѡSL[P]SL[P](R)=p(R)
.ȻNJ[A1,A2]NJ[A1,A2](R1,R2)=R1A1=A2 R2
.UN UN(R1,R2)=R1R2
.INTINT(R1,R2)=R1R2
.DFDF(R1,R2)=R1R2
.EXTEND[A1,...,An;f1,...,fn](R)RA1,...,An,ȡֵΪf1,...,fnRԪĽ(f1,...,fnR)
.LOOKUP[A1,A2,...,A2k,P] 
LOOKUP[A1,A2,...,A2k,P](R1,R2,...,Rk+1)
=R1(R1
.ORDER[A,K,ASCDESC]һ.ORDER[A,K,ASCDESC](R)RԪ鰴A(ASC)(DESC),ֻȡǰKԪ.һϵһ.Ȼƻ˲ѯķ,,ûݲѯĽһ,,Ҫĳ˳ǱҪ.
MOQLжν,DB2 SQL䶨£
.BEFOREt,AFTERt,INt,OVERLAPt ΪBtP,AtP,ItP,OtP
.CONSTAINSΪCoP
.BEFORE,MEETS,OVELAPS,DURING,STARTS,FINISHESEQUALSΪBsP,MsP,OsP,DsP,SsP,FsPEsP.
4.5 Ż
Żб任
(1) PJ[A](OP(R1,R2))OP(PJ[A](R1),PJ[A](R2)),OP{INT,UN,DF}
(2) UN(SL[P1](R),SL[P2](R)SL[P1 or P2](R)
(3) INT(SL[P1](R),SL[P2](R))SL[P1 and P2](R)
(4) SL[P](OP(R1,R2))OP(SL[P](R1),SL[P](R2))
(5) PJ[S](SL[P](R))SL[P](PJ[S](R)),SPԣ
(6) PJ[S](NJ[A1,A2](R1,R2))NJ[A1,A2](PJ[S](R1),PJ[S](R2)),A1A2ͬS
(7) EXTEND[U,f](PJ[S](R))PJ[S,U](EXTEND[U,f](R)),fʹõSУ
(8) EXTEND[U,f](SL[P](R))SL[P](EXTEND[U,f](R))
(9) EXTEND[U,f](OP(R1,R2))OP(EXTEND[U,f](R1),EXTEND[U,f](R2))
(10) EXTEND[U,f](LOOKUP[A1,A2,...,A2k,P](R1,R2,...,Rk+1))LOOKUP [A1,A2,...,A2k,P](EXTEND[U,f](R1),R2,...,Rk+1)
(11) PJ[S](LOOKUP[A1,A2,...,A2k,P](R1,...,Rk+1))LOOKUP[A1,A2,...,A2k,P] (PJ[S](R1),R2,...,Rk+1)),SA1
(12)SL[Q](LOOKUP[A1,A2,...,A2k,P](R1,R2,...,Rk+1))LOOKUP[A1,A2,...,A2k,P] (SL[Q](R1),R2,...,Rk+1)).
1. ݸӵĶ,йȷ.
֤¼.
4.6 ɴȡ
ȡɹ̽ʽеĴӷɺж̬SQLC++set̵DB2ݿʹ.
ӶӦSQL£
.PJ[A](R)SELECT A FROM R
.SL[P](R)SELECT * FROM R WHERE P
.NJ[A1,A2](R1,R2)SELECT * FROM R1 r1, R2 r2 WHERE r1.A1=r2.A2
.UN(R1,R2)R1 UNION R2
.INT(R1,R2)R1 INTESECT R2
.DF(R1,R2)R1 EXCEPT R2
.EXTEND[A1,...,An;f1,...,fn](R)SELECT *,f1(B1) AS A1,...,fn(Bn) AS An FROM R(B1,...,BnΪR)
.LOOKUP[A1,A2,...,A2k,P](R1,...,Rk+1)
SELECT *
FROM R1
WHERE A1 IN (SELECT A2
FROM R2
WHERE A3 IN (...(SELECT A2kFROM Rk+1WHERE P)...))
ORDER[A1,K,ASCDESC](R)һж̬SQLCԹ.
4.7ִдȡ
ɵĺж̬SQLĲѯDB2ϵͳ,õĶOID.
5С
Ҫ۶ýݿѯMOQLԼѯ.MOQLܹ֧͡ṹͬϵʱϵݲѯġ򵥵Ķýݿѯ.DB2ݿΪ洢Ƶ MOQLԲѯ.ѯ,ûMOQLѯΪԴ,DB2ݿеĺж̬SQLDB2ѯΪĿ,һΪѯŻڲֻ,һ任ԱдŻ.
δĹ(1) MOQLԵı.(2) 걸ĴӼŻ.(3) ڴģ͵Ż.(4) оַǽṹýݲѯ.
оõȻѧ𡢹863߿ƼĿ͹ҽʿ.ƽ,1968,ʿ,ʦ,ҪоΪݿ,ýݿ.,1964,ʿ,,ҪоΪݿ,ͨ.ܰӢ,1965,ʿ,,ʿʦ,ҪоΪݿۼӦ.ʩ,1936,,ʿʦ,ҪоΪݿۼӦ.
ͨѶϵ:ƽ,Ϻ200433,ѧѧϵ
ߵλѧѧϵϺ200433
ο
1Woelk D, Kim W. An extensible framework for multimedia information management. Data Engineering, 1987,(3):115121
2Goble C, Docherty M O et al. The Manchester multimedia information system.In: Goos G, Hartmanis J eds. Proceedings of the International Conference Extending Database Technology. Berlin: Springer-Verlag, 1992. 3955
3Little T D. A frame work for synchronization delivery of time-dependent multimedia data. Multimedia Systems, 1993,1(1):8794
4Karmouch A, Emery J. A playback schedule model for multimedia documents. IEEE Multimedia, 1996,(3):5061
5Megalni C, Rabitli F et al. Conceptual modeling of multimedia documents. IEEE Computer, 1991,24(10):2329
6Flicker M, Sawhney H et al. Query by image and video content: the QBIC system. IEEE Computer, 1995,28(9):2231
7Gupta A, Weymouth T E, Jain R. Semantic queries with pictures: the VIMSYS model. In: Lohman M, Sernadas A, Camps R eds. Proceedings of the 17th International Conference Very Large Databases. Barcelona: Morgan Kaufmann Publishers, Inc., 1991. 6979
8Wu J K et al. CORE: a content-based retrieval engine for multimedia information systems. Multimedia Systems, 1995,3(1):4352
9Oomoto E, Tanaka K. OVID: design and implementation of a video-object database system. IEEE Transactions on Knowledge and Data Engineering, 1993,5(4):629643
10Allen J F. Maintaining knowledge about temporal intervals. Communications of ACM, 1983,26(11):832843


¼
1֤:
(1) ɹϵ֪任(1)(6)ȷ.Ҫ֤(7)(12)ȷ.
(2) (7)󲿣EXTEND[U,f](PJ[S](R))=EXTEND[U,f]({ss=S(r)rR})={(s,u)s=S(r)rRu=f(r)},
(7)ҲPJ[S,U](EXTEND[U,f](R))=[S,U]({(r,u)rRu=f(r)})={(s,u)s=s(r)rR(u=f(r)},
ʹ(7).
(3) (8)󲿣EXTEND[U,f](SL[P](R))=EXTEND[U,f]({rP(r)rR})={(r,u)P(r)rRu=f(r)},
(8)ҲSL[P](EXTEND[U,f](R))=p{(r,u)rRu=f(r)}={(r,u)P(r)rRu=f(r)},
ʹ(8).
(4) ֤OPΪUNʱ,֤׵.
(9)󲿣EXTEND[U,f](UN(R1,R2))=EXTEND[U,f]({rrR1rR2})={(r,u)(rR1u=f(r))(rR2u=f(r))},
(9)ҲUN(EXTEND[U,f](R1),EXTEND[U,f](R2))=UN({(r,u)rR1u=f(r)},{(r,u)rR2u=f(r)})={(r,u)(rR1u=f(r))(rR2u=f(r))},
ʹ(9).
(5) (10)󲿣EXTEND[U,f](LOOKUP[A1,A2,...,A2k,P](R1,R2,...,Rk+1))

(10)ҲLOOKUP[A1,A2,...,A2k,P](EXTEND[U,f](R1),R2,...,Rk+1)

ʹ(10).
(6) (11)󲿣PJ[S](LOOKUP[A1,A2,...,A2k,P](R1,...,Rk+1))

(11)Ҳ LOOKUP[A1,A2,...,A2k,P](PJ[S](R1),R2,...,Rk+1))

ʹ(11).
(7) (12)󲿣SL[Q](LOOKUP[A1,A2,...,A2k,P](R1,R2,...,Rk+1))

=LOOKUP[A1,A2,...,A2k,P](SL[Q](R1),R2,...,Rk+1)
=(12)Ҳ.
(1)(7)֪,1.
1998-04-16յԭ 
1998-08-04յ޸ĸ
