interactwebdb

InteractiveQueryandSearchinSemistructuredDatabases

RoyGoldman,JenniferWidom

StanfordUniversityroyg,widom@cs.stanford.edu

www-db.stanford.edu

Abstract

Semistructuredgraph-baseddatabaseshavebeenproposed

aswell-suitedstoresforWorld-WideWebdata.Yetsofar,

languagesforqueryingsuchdataaretoocomplexforca-

sualWebusers.Further,proposedqueryapproachesdo

nottakeadvantageoftheinteractivenatureoftypicalWeb

sessions—usersareproficientatiterativelyrefiningtheir

Webexplorations.Inthispaperweproposeanewmodel

forinteractivelyqueryingandsearchingsemistructured

databases.Userscanbeginwithasimplekeywordsearch,

dynamicallybrowsethestructureoftheresult,andthen

submitfurtherrefiningqueries.Enablingthismodelex-

posesnewrequirementsofasemistructureddatabaseman-

agementsystemthatarenotapparentundertraditional

databaseuses.Wedemonstratetheimportanceofefficient

keywordsearch,structuralsummariesofqueryresults,

andsupportforinversepointers.Wealsodescribesome

preliminarysolutionstothesetechnicalissues.

1Introduction

QueryingtheWebhasunderstandablygatheredmuchat-

tentionfrombothresearchandindustry.Forsearchingthe

entireWeb,searchenginesareawell-proven,successful

technology[Dig97,Ink96].Searchenginesassumelittle

aboutthesemanticsofadocument,whichworkswellfor

theconglomerationofdisparatedatasourcesthatmakeup

theWeb.ButforsearchingwithinasingleWebsite,a

searchenginemaybetoobluntatool.LargeWebsites,

withthousandsofpages,areattractingmillionsofusers.

TheESPNSportssite(espn.com),forexample,hasover

90,000pages[Sta96]andseveralmillionpageviewsaday

[Sta97].Aslargeassomesitesmaybe,theyarefunda-

mentallydifferentfromtheWebasawholesinceasingle

siteusuallyhasacontrolledpointofadministration.Thus,

itbecomespossibletoconsistentlyassignandexposetheforobject-relationalandrelationaldatabases,respectively,

enableuserstospecifyqueriesinasimilarmanner.)A

DataGuidesummarizesallpathsthroughadatabase,start-

ingfromitsroot.Whilesuchdynamicsummariesarean

importantbasictechnologyforseveralreasons[GW97],

presentingtheuserwithacompletesummaryofpaths

maystillforcehimtoexploremuchunnecessarydatabase

structure.

Inthispaper,targetingcasualusers,ourstrategyisto

modelandexploittwokeytechniquesthatWebusersare

intimatelyfamiliarwith:

1.specifyingasimplequerytobeginasearch,usually

withkeywords

2.furtherexploringandrefiningtheresults

Forthefirsttechnique,wewanttosupportverysimple

queriesthathelp“focus”theuseronrelevantdata.The

manysearchenginesontheWebhaveshownthatkeyword

searchisaneasyandeffectivetechniqueforbeginninga

search.Toenablethesecondtechnique,wewanttoexpose

andsummarizethestructureofthedatabase“surround-

ing”anyqueryresult.Todothis,wedynamicallybuild

andpresentaDataGuidethatsummarizespathsnotfrom

thedatabaseroot,butinsteadfromtheobjectsreturned

inthequeryresult.Ausercanthenrepeattheprocess

bysubmittingaqueryfromthis“focused”DataGuideor

specifyingadditionalkeywords,ultimatelylocatingthe

desiredresults.

OurdiscussionsareinthecontextoftheLoreproject

[MAG97],whichusestheOEMgraph-baseddatamodel

[PGMW95]andtheLorelquerylanguage[AQM97].

Ourresultsareapplicabletoothersimilargraph-baseddata

models,aswellastheemergingXMLstandardfordefining

thesemanticstructureofWebdocuments[Con97].

Intherestofthepaper,wefirstprovidebackground

andcontextinSection2.InSection3,wepresentasimple

motivatingexampletoillustratewhynewfunctionalityis

neededinasemistructureddatabasesystemtosupportin-

teractivequeryandsearch.Oursessionmodelisdescribed

inSection4,followedbythreesectionscoveringthenew

requiredtechnology:

Keywordsearch(Section5):Efficientdatastruc-

turesandindexingtechniquesareneededforquickly

findingobjectsthatmatchkeywordsearchcriteria.

Whilewemayborrowheavilyfromwell-provenin-

formationretrieval(IR)technology,thenewcontext

ofagraphdatabaseissufficientlydifferentfroma

simplesetofdocumentstowarrantinvestigation.

DataGuideenhancements(Section6):Computing

aDataGuideovereachqueryresultcanbevery

expensive,sowehavedevelopednewalgorithmsfor

computingandpresentingDataGuidespiecewise,

computingmoreondemand.Inversepointers(Section7):Tofullyexposethe

structuralcontextofaqueryresult,itiscrucial

toexploitinversepointerswhencreatingtheData-

Guidefortheresult,browsingthedata,andsub-

mittingrefiningqueries.Whilesupportforin-

versepointersmayseemstraightforward,themajor

proposedmodelsforsemistructureddataarebased

ondirectedgraphs,andinversepointershavenot

beenconsideredintheproposedquerylanguages

[AQM97,BDHS96,FFLS97].

2Background

Tosetthestagefortherestofthepaper,webrieflydescribe

theOEMdatamodel,introducetheLorelquerylanguage,

andsummarizeDataGuides.InOEM,eachobjectcontains

anobjectidentifier(oid)andavalue.Avaluemaybe

atomicorcomplex.Atomicvaluesmaybeintegers,reals,

strings,images,oranyotherindivisibledata.Acomplex

OEMvalueisacollectionofOEMsubobjects,eachlinked