SIGMOD 2005 Efficient Keyword Search for Smallest LCAs in XML Databases
Ef?cient Keyword Search for Smallest LCAs in XML
Databases
Yu Xu
Department of Computer Science&Engineering University of California,San Diego
yxu@https://www.wendangku.net/doc/f06039764.html,
Y annis Papakonstantinou Department of Computer Science&Engineering University of California,San Diego
yannis@https://www.wendangku.net/doc/f06039764.html,
ABSTRACT
Keyword search is a proven,user-friendly way to query HTML documents in the World Wide Web.We propose keyword search
in XML documents,modeled as labeled trees,and describe corre-sponding ef?cient algorithms.The proposed keyword search re-turns the set of smallest trees containing all keywords,where a tree
is designated as“smallest”if it contains no tree that also contains
all keywords.Our core contribution,the Indexed Lookup Eager al-gorithm,exploits key properties of smallest trees in order to outper-form prior algorithms by orders of magnitude when the query con-tains keywords with signi?cantly different frequencies.The Scan Eager variant is tuned for the case where the keywords have similar frequencies.We analytically and experimentally evaluate two vari-ants of the Eager algorithm,along with the Stack algorithm[13]. We also present the XKSearch system,which utilizes the Indexed Lookup Eager,Scan Eager and Stack algorithms and a demo of which on DBLP data is available at
https://www.wendangku.net/doc/f06039764.html,/projects/xksearch.Finally, we extend the Indexed Lookup Eager algorithm to answer Lowest Common Ancestor(LCA)queries.
1.INTRODUCTION
Keyword search is a proven user-friendly way of querying HTML documents in the World Wide Web.Keyword search is well-suited
to XML trees as well.It allows users to?nd the information they are interested in without having to learn a complex query language
or needing prior knowledge of the structure of the underlying data [1,5,12,15,16,18].For example,assume an XML document named“School.xml”,modeled using the conventional labeled tree model in Figure1,that contains information including classes,projects, etc.A user interested in?nding the relationships between“John”and“Ben”issues a keyword search“John,Ben”and the search sys-tem returns the most speci?c relevant answers-the subtrees rooted
at nodes,and.The meaning of the answers is obvious to the user:“Ben”is a TA for“John”for the CS2A class,“Ben”is a student in the CS3A class taught by“John”,both“John”
School
Figure1:School.xml(each node is associated with its Dewey number)
answer
for$a in document(‘‘School.xml’’)//*
where empty(for$b in$a/*
where some$c in$b//*
satisfies$c=‘‘John’’
and some$c in$b//*
satisfies$c=‘‘Ben’’
return$b)
and some$d in$a//*satisfies$d=‘‘John’’and some$d in$a//*satisfies$d=‘‘Ben’’return$a
/answer
Figure2:XQuery:?nd answers for“John,Ben”
often by orders of magnitude when the keywords in the query have different frequencies,and loses only by a small margin when the keywords have similar frequencies.Indeed in the DBLP demo,only the Indexed Lookup Eager algorithm is used.
In Section2we introduce the notation and de?nitions used in the paper.Section3presents the SLCA problem and its solutions.We discuss the Indexed Lookup Eager and the Scan Eager algorithms, and the sort-merge based Stack algorithm[13].Section3also pro-vides the complexity of the main memory implementations of the algorithms.In Section4,we discuss the XKSearch implementation of the Indexed Lookup Eager,Scan Eager and Stack algorithms and provide their complexity in terms of number of disk accesses. In Section5,we discuss the All Lowest Common Ancestor(LCA) problem and extend the SLCA’s Indexed Lookup algorithm to ef?-ciently?nd LCAs in“shallow”trees.Our experimental results are discussed in Section6.We discuss related work in Section7and conclude in Section8.
2.NOTATION
We use the conventional labeled ordered tree model to repre-sent XML trees.Each node of the tree corresponds to an XML element and is labeled with a tag.We assign to each node a numerical id that is compatible with preorder numbering,in the sense that if a node precedes a node in the preorder left-to-right depth-?rst traversal of the tree then. The XKSearch implementation uses Dewey numbers as the id’s. Prior work has shown that Dewey numbers are a good id choice [23].In addition,Dewey numbers provide a straightforward so-lution to locating the LCA of two nodes.The usual relation-ship is assumed between any two Dewey numbers.For example,
.Obviously the relationship on Dewey num-bers is compatible with the requirement for preorder numbering. Given a list of keywords and an input XML tree, an answer subtree of keywords is a subtree of such that it contains at least one instance of each keyword.
A smallest answer subtree of keywords is an answer subtree(of keywords)such that none of its subtrees is an answer subtree(of keywords).The result
of a keyword search on an input XML tree,is the set of the roots of all smallest answer subtrees of.For presentation brevity,we do not explicitly refer to the input XML tree and simply write when is obvious.
Given a list of keywords and an input XML tree, we assume denotes the keyword list of,i.e.,the list of nodes whose label directly contains sorted by id.denotes that node is an ancestor of node;denotes that or .Given a node,is called an ancestor node in if there exists a node in such that.When the set is implied by the context,we simply say is an ancestor node.Notice that if then,and the other direction is not always true.
The function computes the lowest common an-cestor or LCA of nodes and returns null if any of the arguments is null.Given two nodes,and their Dewey num-bers,,is the node with the Dewey number that is the longest common pre?x of and and the cost of comput-ing is where is the maximum depth of the tree. For example,the LCA of nodes and is the node in Figure1.Given sets of nodes,a node belongs to if there exist such that
.Then is called an LCA of sets.
A node belongs to the smallest lowest common ancestor(SLCA)
of if and
.is called a SLCA of sets if
.
Notice that the query result is
and that=
where removes ancestor nodes from its input. The function computes the right match of in a set, that is the node of that has the smallest id that is greater than or equal to;computes the left match of in a set, that is the node of that has the biggest id that is less than or equal to1.()returns null when there is no right (left)match node.The cost of()is
since it takes steps(Dewey number comparisons)to?nd the right(left)match node and the cost of comparing two Dewey numbers is.The function returns the other argument when one argument is null and returns the descen-dant node when and have ancestor-descendant relationship. The cost of the function is.
3.ALGORITHMS FOR FINDING THE SLCA
OF KEYWORD LISTS
This section presents the core Indexed Lookup Eager algorithm, its Scan Eager variation and the prior work Stack algorithm[13].
A brute-force solution to the SLCA problem computes the LCAs of all node combinations and then removes ancestor nodes.Its complexity is.Besides being inef?cient the brute-force approach is blocking.After it computes an LCA
for some,,,it cannot report as an answer since there might be another set of nodes
such that.
The complexity analysis given in this section is for main memory cases.We will give disk access complexity in Section4after we discuss the implementation details of how we compress and store keyword lists on disk.In the sequel we choose to be the smallest keyword list since,where is any permutation of,and there is a bene?t in using the smallest list as as we will see in the complexity analysis of the algorithms.
3.1The Indexed Lookup Eager Algorithm(IL) The Indexed Lookup Eager algorithm is based on four properties of SLCAs,which we explain starting from the simplest case where and is a singleton.
According to the above Property(1),we compute the LCA of and its left match in,the LCA of and its right match in,and the singleton formed from the deeper node from the two LCAs is .Property(1)is based on the following two observa-tions.For any two nodes to the right(according to preorder) of a node,if,then
;similarly,for any two nodes to the left of a node ,if,then2. We generalize to arbitrary when the?rst set is a singleton. Notice the recursiveness in Property(2).
,based on the following two lemmas, computes ef?ciently by removing ancestor nodes on the?y.
L EMMA 1.Given any two nodes and a set,if
and,
then.
L EMMA 2.For any two nodes and a set such that
and, if is not an ancestor of,then for any such that,. Consider sorted by id,where.Let
where,,. According to Lemma1,if where node ap-pears after in(that is,),then is an ancestor node.Thus when computing the list,we can discard the out-of-order nodes such as.The resulting list is in order and contains the nodes of.However is not necessarily ancestor node free. Consider any two adjacent nodes,in where is after .If is not an ancestor of,then cannot be an ancestor of any node that is after in(according to Lemma2),which means is a of,.Lemma1and2together lead to the subroutine
applies Lemma1to remove out-of-order nodes,and lines#6-8apply Lemma2to identify a SLCA as early as possible. As can be seen from
line#6is true in the fourth iteration,and(node)is deter-mined to be a SLCA(line#7).Then(line#8).In the last iteration,,,and node is deter-mined to be a SLCA(line#7).Finally node is returned as a SLCA(line#10).Thus the answer to“John Ben”is[,, ].
subroutine
to compute
ef?ciently:
based on the following Property(4),
An algorithm based on
by adding“eagerness”-it returns the?rst part of the answers without having to completely go through any of the keyword lists and it pipelines the delivery of SLCAs.Assume there is a memory buffer size of nodes.The Indexed Lookup Eager al-gorithm?rst computes where is the?rst nodes of.Then it computes and so on, until it computes.All nodes in except the last node are guaranteed to be SLCAs because of Lemma1and2and are returned.The last node of(in line #10)is carried on to the next operation(lines#6-9)to be determined whether it is a or not.The above operation is repeated for the next nodes of until all nodes in have been processed. The smaller is,the faster the algorithm produces the?rst SLCA. If,again only three nodes are needed to be kept in memory in the whole process.However,a smaller may delay the compu-tation of all SLCAs when considering disk accesses.If, the Indexed Lookup Eager algorithm is exactly the same as the al-gorithm based on
(
(,)=.Initially. Line#6-9has no effect.As mentioned before,every node in ex-cept the last one is a SLCA and returned(line#10,#11).In the ?rst iteration,line#11outputs nothing and(node)is car-ried to the next iteration to be determined whether it is a SLCA or not.In the second iteration of loop at line#2,the rest nodes of is read,=[,](line#3).After executing line #4and#5,0.1.2.0.00.2.0.0.0, which is
6if()
7removeFirstNode(B)
8if()
9output
10
11output;=
12
13output
3.2Scan Eager Algorithm
When the occurrences of keywords do not differ signi?cantly,the total cost of?nding matches by lookups may exceed the total cost of?nding matches by scanning the keyword lists.We implement a variant of the Indexed Lookup Eager Algorithm,named Scan Ea-ger Algorithm,to take advantage of the fact that the accesses to any keyword list are strictly in increasing order in the Indexed Lookup Eager algorithm.The Scan Eager algorithm is exactly the same as the Indexed Lookup Eager algorithm except that its and im-plementations scan keyword lists to?nd matches by maintaining a cursor for each keyword list.In order to?nd the left and right match of a given node with id in a list,the Scan Eager algo-rithm advances the cursor of until it?nds the node that is closest to from the left or the right side.Notice that nodes from different lists may not be accessed in order,though nodes from the same list are accessed in order.
The complexity of the Scan Eager algorithm is(+
),or because there are Dewey num-ber comparisons,and operations.
3.3The Stack Algorithm
The stack based sort-merge algorithm(DIL)in XRANK[13], which also uses Dewey numbers,is modi?ed to?nd SLCAs and is called the Stack Algorithm here.Each stack entry has a pair of components.Assume the components from the bottom entry to a stack entry are respec-tively.Then the stack entry denotes the node with the Dewey number.is an array of length of boolean values where means that the subtree rooted at the node denoted by the stack entry directly or indirectly
J B C
0F 0F 0F
F T
F F
T F
(b)node
0F
0F
0F
1F
0F
F T
T T
T T (d)node 0F
1F
1F
1F
0F
F F
F F
T T
F F
T T
(f)node
2F
1F
0F
1
3For the sake of this example,we neglect that.
Figure4:B+tree from the data of Figure1for Scan Eager and Stack algorithms may lead to a SLCA or not until it comes to process node
and it has to repeatedly compute the longest common an-
cestor of each node with the node represented by the top entry
of the stack.Notice that the“Class”list may have arbitrarily many
nodes after node and before node4that Stack has to
access but Scan Eager does not need to.
4.XKSEARCH SYSTEM IMPLEMENTATION
In this section we present the architecture of the XKSearch im-
plementation,then discuss how the keyword lists are compressed
and stored on disk-based B tree index structures,and?nally pro-
vide disk access complexity analysis summarized in Table1for the
three algorithms discussed in Section3-Indexed Lookup Eager,
Scan Eager and Stack.
We implemented the Indexed Lookup Eager,Scan Eager and
Stack algorithms in Java using the Apache Xerces XML parser and
Berkeley DB[4].The architecture of the implementation(XK-
Search)is shown in Figure6.The LevelTableBuilder reads an in-
put XML document and outputs a level table.The inverted
index builder reads in the level table and outputs a keyword list
for each keyword in.Those keyword lists are stored in a B-tree structure that allows ef?cient implementation of the match operations.
The index builder also generates a frequency table,which records the frequencies of keywords in,is read into memory by the ini-tializer,and is stored as a hash table.The query engine accepts a keyword search,uses the frequency hash table to locate the small-est keyword list,executes the Indexed Lookup Eager,Scan Eager and the Stack algorithms and returns all SLCAs.
For performance reasons,Dewey numbers are compressed.We introduce a level table with entries where is the depth of the input tree.The entry denotes the maximum number of bits needed to store the-th component in a Dewey number,i.e.,
,where is the number of children of the node at the level of that has the maximum number of children among all nodes at the same level.The root is at level,5.In general
135
131
There are two types of B tree structures implemented in XK-Search;the?rst is for the Indexed Lookup Eager algorithm,the second is for the Scan Eager and the Stack algorithms.In the im-plementation of the Indexed Lookup Eager algorithm,we put all keyword lists in a single B+tree where keywords are the primary key and Dewey numbers are the secondary key(See Figure5where
.is the average num-ber of nodes in a disk block of and is the number of nodes in the keyword list.depends on the page size,the depth of the XML tree,and the maximum out-degrees of nodes at each
level.is at least
Figure 5:B+tree from the data of Figure 1for Indexed Lookup Eager Algorithm
Figure 6:XKSearch Architecture
Figure 7:Finding all LCAs
ancestor of each node in check whether is an LCA,as explained next.
Let be a SLCA.Consider any node that is an ancestor of (See Figure 7).If the subtree rooted at contains a node with a keyword,say ,that is not under node and is not an ancestor of ,then is an LCA.To determine whether contains such a node we use at most two lookups.The nodes under but not under are divided into two parts by the path from to .Let node be the right match node of in (the keyword list of ).If node is not under and is not under ,then is in the left part of (otherwise would be under because is a SLCA)which means is an LCA.Next,let be the child of on the path from to .If the Dewey id of is then the Dewey id of is ,where is the ordinal number of among its siblings.The node ,which is the immediate right sibling of ,has Dewey number
and is called the uncle node of under .Let be the
right match node of in .If ,then is in the right side of ,which makes an LCA.The existence of any node containing a keyword from under but not under can be checked similarly.The subroutine in Algorithm 3is based on the above observations.
Since a node might be an ancestor node of multiple SLCAs,we want to avoid repeatedly checking whether is an LCA.Instead of maintaining some data structures to record whether a node has been identi?ed as an LCA or not,we use an approach that only needs to keep three nodes in memory.Let be the ?rst three nodes (see Figure 7)in the list of SLCAs produced by the Eager algorithm,and let .For each node in the path from to ,we check whether is an LCA or not.Then
we check each node in the path from to 6
,and
so on.Algorithm 3is based on this approach and guarantees that each of the ancestor nodes of all SLCAs is checked exactly once.Notice that in Algorithm 3we do not need to produce all SLCAs ?rst.Algorithm 3pipelines the delivery of LCAs since Algorithm IL pipelines the delivery of SLCAs.
The number of disk accesses of Algorithm 3is .The
main memory complexity of Algorithm 3is
.Finding all SLCAs costs .Checking whether the
ancestors of the
are LCAs or not costs since we need to check nodes and checking each node
costs
.A LGORITHM 3
(C OMPUTING ALL LCA S ).
?ndLCA(List L)
//is the list of SLCAs
;
while has more nodes
=;
=removeHead();current-lca=lca(,);
for each ancestor node of until current-lca //not including current-lca
if (checkLCA(,)==true)output .
boolean checkLCA()
for to =rm(,)if ()return true;for to
=the uncle node of under ;
;
if (
)return true;return false;
6.EXPERIMENTS
We have run XKSearch on the DBLP data 7.We ?lter out citation and other information only related to the DBLP website and group ?rst by journal/conference names,then by years.The experiments have been done on a 1.2GHz laptop with 512MB of RAM.An online demo,which enables keyword search in the same grouped 83MB DBLP data used in the experiments is provided at https://www.wendangku.net/doc/f06039764.html,/projects/xksearch .
The demo runs as a Java Servlet using Apache Jakarta Tom-cat server.The Xalan engine is used to translate XML results to HTML.
We evaluate the Scan Eager,Indexed Lookup Eager and Stack al-gorithms discussed in Section 4for the SLCA semantics by varying the number and frequencies of keywords both on hot cache (Fig-ures 8,9and 10)and on cold cache (Figures 11,12and 13).
A program randomly chose forty queries for each experiment.The response time of each experiment on hot cache in Figures 8,9
main memory
complexity accesses#
operations
IL
Scan
Stack
(a)Legend
(b)small frequency=10
(c)small
frequency=100(d)small frequency=1000
Figure8:#Keywords=2,keeping the small frequency constant,varying the frequency of the large keyword list(hot cache)
(a)
frequency(10,100000)(b)frequency(100,100000)
(c)frequency(1000,100000)
(d)frequency(10000,100000)
Figure9:Varying the number of keywords,keeping frequencies constant(hot cache)
(a)small frequency(10)
(b)medium frequency(100)
(c)high frequency(1000)
(d)large frequency(10000)
Figure 10:Varying the number of keywords,all keyword lists having the same size (hot
cache)
(a)small
frequency=10
(b)small
frequency=100
(c)small frequency=1000
Figure 11:#Keywords=2,keeping the small frequency constant,varying the frequency of the large keyword list (cold cache)
(a)frequency(10,100000)
(b)frequency(100,100000)
(c)
frequency(1000,100000)(d)frequency(10000,100000)
Figure 12:Varying the number of keywords,keeping frequencies constant (cold
cache)
(a)small
frequency(10)
(b)medium
frequency(100)
(c)high
frequency(1000)(d)large frequency(10000)
Figure 13:Varying the number of keywords,all keyword lists having the same size (cold cache)
based on the concept of MLCA(Meaningful Lowest Common An-cestor)where the set of MLCAs of sets,...,is the same as
.The complexity of the stack based algorithm proposed in[18]to compute the set of MLCAs of,...,, which is similar to the sort merge stack algorithm in XRANK,is ,the same as that of the Scan and Stack algorithms.Sim-ilar to[14],[18]returns the set of MLCAs with explanations on why each node is an MLCA.
A popular numbering scheme is to use a pair of numbers consist-ing of preorder and postorder numbers[2,17].Given two nodes and their pairs of numbers,it can be determined whether one of them is an ancestor of the other in constant time.However,this type of scheme is inef?cient in?nding the LCA of two nodes. Tree query patterns for querying XML trees have received great attention and ef?cient approaches are known[3,7,22].These ap-proaches are not applicable for the keyword searching problem be-cause given a list of keywords,the number of tree patterns from the keywords is exponential in the size of the schema of the input document and the number of keywords.
Finally there are research prototypes and commercial products that allow keyword searches on a collection of XML documents and return a list of(ranked)XML documents that contain the key-words[19,27].
8.CONCLUSIONS
The XKSearch system inputs a list of keywords and returns the set of Smallest Lowest Common Ancestor nodes,i.e.,the list of nodes that are roots of trees that contain the keywords and contain no node that is also the root of a tree that contains the keywords. For each keyword the system maintains a list of nodes that con-tain the keyword,in the form of a tree sorted by the id’s of the nodes.The key property of SLCA search is that,given two key-words and and a node that contains keyword,one need not inspect the whole node list of keyword in order to discover potential solutions.Instead,one only needs to?nd the left and right match of in the list of,where the left(right)match is the node with the greatest(least)id that is smaller(greater)than or equal to the id of.The property generalizes to more than two keywords and leads to the Indexed Lookup Eager algorithm,whose main memory complexity is where is the max-imum depth of the tree,is the number of keywords in the query, and()is the minimum(maximum)size of keyword lists through.Assuming a B-tree disk-based structure,where the non-leaf nodes of the B-tree are cached in main memory the num-ber of disk accesses needed is.
The analytical results,as well as the experimental evaluation, show that the Indexed Lookup Eager algorithm outperforms,often by orders of magnitude,other algorithms when the keywords have different frequencies.We provide the Scan Eager algorithm as the best variant for the case where the keywords have similar frequen-cies.The experimental evaluation compares the Indexed Lookup Eager,Scan Eager and Stack(described in[13])algorithms.
The XKSearch system is implemented,using the BerkeleyDB [4]B-tree indices and a demo of it on DBLP data is available at https://www.wendangku.net/doc/f06039764.html,/projects/xksearch.
9.REFERENCES
[1]S.Agrawal,S.Chaudhuri,and G.Das.DBXplorer:A system
for keyword-based search over relational databases.In ICDE, 2002.
[2]V.Aguilera et al.Querying XML documents in XYleme.In
SIGIR Workshop on XML and Information Retrieval,2000.
[3]S.Amer-Yahia,S.Cho,and D.Srivastava.Tree pattern
relaxation.In EDBT,2002.
[4]BerkeleyDB.https://www.wendangku.net/doc/f06039764.html,/.
[5]G.Bhalotia,A.Hulgeri,C.Nakhe,S.Chakrabarti,and
S.Sudarshan.Keyword searching and browsing in databases using BANKS.In ICDE,2002.
[6]S.Brin and L.Page.The anatomy of a large-scale
hypertextual Web search https://www.wendangku.net/doc/f06039764.html,puter Networks and
ISDN Systems,30(1-7):107–117,1998.
[7]Z.Chen,H.Jagadish,F.Korn,and N.Koudas.Counting twig
matches in a tree.In ICDE,2001.
[8]S.Cohen,J.Namou,Y.Kanza,and Y.Sagiv.XSEarch:A
semantic search engine for XML.In VLDB,2003.
[9]D.Florescu,D.Kossmann,and I.Manolescu.Integrating
keyword search into XML query processing.In WWW9,
2000.
[10]N.Fuhr and K.Grojohann.XIRQL:A Query Language for
Information Retrieval in XML documents.In SIGIR,2001.
[11]H.Garcia-Molina,J.Ullman,and J.Widom.Database
System Implementation.Prentice-Hall,2000.
[12]R.Goldman,N.Shivakumar,S.Venkatasubramanian,and
H.Garcia-Molina.Proximity Search in Databases.In VLDB,
1998.
[13]L.Guo,F.Shao,C.Botev,and J.Shanmugasundaram.
XRANK:Ranked keyword search over XML documents.In SIGMOD,2003.
[14]V.Hristidis,N.Koudas,Y.Papakonstantinou,and
D.Srivastava.Keyword Proximity Search in XML Trees.
Available at
https://www.wendangku.net/doc/f06039764.html,/publications/treeproximity.pdf. [15]V.Hristidis and Y.Papakonstantinou.Discover:Keyword
search in relational databases.In VLDB,2002.
[16]V.Hristidis,Y.Papakonstantinou,and A.Balmin.Keyword
proximity search on XML graphs.In ICDE,2003.
[17]Q.Li and B.Moon.Indexing and Querying XML data for
regular path expressions.In VLDB,2001.
[18]Y.Li,C.Yu,and H.V.Jagadish.Schema-free xquery.In
VLDB,2004.
[19]J.Naughton et al.The Niagara Internet Query System.IEEE
Data Engineering Bulletin,24(2):27–33,2001.
[20]B.Schieber and U.Vishkin.On?nding lowest common
ancestors:Simpli?cation and parallelization.SIAM J.
Computing,17(6):1253–1262,1988.
[21]A.Schmidt,M.L.Kersten,and M.Windhouwer.Querying
XML documents made easy:Nearest concept queries.In
ICDE,2001.
[22]D.Srivastava et al.Structural joins:A primitive for ef?cient
XML query pattern matching.In ICDE,2002.
[23]I.Tatarinov,S.Viglas,K.Beyer,J.Shanmugasundaram,
E.Shekita,and C.Zhang.Storing and querying ordered
XML using a relational database system.In SIGMOD,2002.
[24]A.Theobald and G.Weikum.Adding relevance to XML.In
WebDB,2000.
[25]A.Theobald and G.Weikum.The index-based XXL search
engine for querying XML data with relevance ranking.In
EDBT,2002.
[26]Z.Wen.New algorithms for the LCA problem and the binary
tree reconstruction https://www.wendangku.net/doc/f06039764.html,rmation Processing.
Lett,51(1):11-16,1994.
[27]XYZFind.https://www.wendangku.net/doc/f06039764.html,/tools/xyz?nd.html.
2017年6月大学英语四级真题试卷及答案(第3套)
2017年6月大学英语四级真题及答案(三) Part I Writing (30 minutes) (请于正式开考后半小时内完成该部分，之后将进行听力考试) Directions:For this part, you are allowed 30 minutes to write an advertisement on your campus website to sell some of the course books you used at college. Your advertisement may include a brief description of their content,their condition ,their price and your contact information. You should write at least 120 words but no more than 180 words. Part II Listening Comprehension (25 minutes) 说明：2017年6月大学英语四级考试全国共考了两套听力.本套的听力内容与第二套相同，因此本套听力部分不再重复给出。 Part ⅢReading Comprehension (40 minutes) Section A Directions: In this section, there is a passage with ten blanks. You are required to select one word for each blank from a list of choices given in a word bank following the passage. Read the passage through carefully before making your choices, Each choice in the bank is identified by a letter. Please mark the corresponding letter for each item on Answer Sheet 2 with a single line through the centre. You may not use any of the words in the bank more than once. Questions 26 to 35 are based on the following passage. As if you needed another reason to hate the gym, it now turns out that exercise can exhaust not only your muscles, but also your eyes. Fear not, however, for coffee can stimulate them again. During (26)_______ exercise, our muscles tire as they run out of fuel and build up waste products. Muscle performance can also be affected by a (27)_______ called "central fatigue,” in which an imbalance in the
历年英语四级真题及答案详解
2009年6月英语四级考试真题与答案真题： Part I Writing (30 minutes) Directions: F or this part, you are allowed 30 minute to write a short essay on the topic of students selecting their lectures. You should write at least 120 words following the outline given bellow: 1. 越来越多的博物馆免费对外开放的目的是什么？ 2. 也会带来一些问题 3. 你的看法？ Free admission to museums Part II Reading Comprehension (Skimming and Scanning) (15 minutes) Directions: In this part, you will have 15 minutes to go over the passage quickly and answer the questions on Answer Sheet 1.For questions 1-7, choose the best answer from the four choices marked A),B),C) and D). For questions 8-10, complete the
sentences with the information given in the passage. How Do You See Diversity? As a manager, Tiffany is responsible for interviewing applicants for some of the positions with her company .During one interview, she noticed that the candidate never made direct eye contact. She was puzzled and somewhat disappointed because she liked the individual otherwise. He had a perfect resume and gave good responses to her questions, but the fact that he never looked her in the eye said “untrustworthy,” so she decided to offer the job to her second choice. “It wasn’t until I attended a diversity workshop that I realized the person we passed over was the perfect person,” Tiffany confesses. What she hadn’t known at the time of the interview was that the candidate’s “different” behavior was simply a cultural misunde rstanding . He was an Asian-American raised in a household where respect for those in authority was shown by averting(避开) your eyes. “I was just thrown off by the lack of ye contact; not realizing it was cultural,” Tiffany says. “I missed out ,but will not miss that opportunity again.” Many of us have had similar encounters with behaviors we perceive
初三数学 坐标与函数
初三数学坐标与函数 1. 如图，方格纸上一圆经过（2，5），（－2，l），（2，－3），( 6，1）四点，则该圆的圆心的坐标为（） A．（2，－1）B．（2，2）C．（2，1）D．（3，l） 2.已知M(3a－9，1－a)在第三象限，且它的坐标都是整数，则a等于（） A．1 B．2 C．3 D．0 3.在平面直角坐标系中，点P（－2，1）关于原点的对称点在（） A．第一象限；B．第M象限； C．第M象限；D．第四象限 4.如图，△ABC绕点C顺时针旋转90○后得到AA′、B′C′， 则A点的对应点A′点的坐标是（） A．（－3，－2）； B．（2，2）； C．（3，0）； D．（2，l） 5.点P(3，－4）关于y轴的对称点坐标为_______，它 关于x轴的对称点坐标为_______．它关于原点的对 称点坐标为_____． 6.李明、王超、张振家及学校的位置如图所示． ⑴学校在王超家的北偏东____度方向上，与王超家 大约_____米。 ⑵王超家在李明家____方向上，与李明家的距离大约是____米； ⑶张振家在学校____方向上，到学校的距离大约是______ 米． 7.东风商场文具部的某种毛笔每支售价25元，书法练习本每本售价5元．该商场为了促销制定了两种优惠方法，甲：买一支毛笔就赠送一本书法练习本；乙：按购买金额打九折付款．某书法兴趣小组欲购买这种毛笔10支，书法练习本x（x＞10）本． （1）写出每种优惠办法实际付款金额y甲(元)、y乙（元）与x（本）之间的关系式；（2）对较购买同样多的书法练习本时，按哪种优惠方法付款更省钱？ 8. 某居民小区按照分期付款的形式福利售房，政府给予一定的贴息，小明家购得一套现价为120000元的房子，购房时首期（第一年）付款30000元，从第二年起，以后每年应付房款为5000元与上一年剩余欠款利息的和，设剩余欠款年利率为0．4%． （1）若第x(x≥2）年小明家交付房款y元，求年付房款y（元）与x(年）的函数关系式；（2）将第三年，第十年应付房款填人下列表格中 9. 如图所示，在直角坐标系中，第一次将△OAB变换成△OA1B1；第二次将OA1B1变换
大学英语四级考试真题及答案完整版
精品文档 2014年6月大学英语四级考试真题及答案（完整版） 来源：文都教育 Part I Writing (30 minutes) Directions: For this part, you are allowed 30 minutes to write a short essay on the following topic. You should write at least 120 words but no more than 180 words. Suppose a foreign friend of yours is coming to visit your hometown, what is the most interesting place you would like to take him/her to see and why? 注意：此部分试题请在答题卡1上作答。 Part II Listening Comprehension (30 minutes) Section A Directions: In this section, you will hear 8 short conversations and 2 long conversations. At the end of each conversation, one or more questions will be asked about what was said. Both the conversation and the questions will be spoken only once. After each question there will be a pause. During the pause, you must read the four choices marked A), B), C) and D), and decide which is the best answer. Then mark the corresponding letter on Answer Sheet 1 with a single line through the centre. 注意：此部分试题请在答题卡1上作答。 1. A) See a doctor about her strained shoulder. B) Use a ladder to help her reach the tea. C) Replace the cupboard with a new one. D) Place the tea on a lower shelf next time. 2. A) At Mary Johnson's. C) In an exhibition hall. B) At a painter's studio. D) Outside an art gallery. 3. A) The teacher evaluated lacks teaching experience. B) She does not quite agree with what the man said. C) The man had better talk with the students himself. D) New students usually cannot offer a fair evaluation. 4. A) He helped Doris build up the furniture. B) Doris helped him arrange the furniture.
SQL常见语句及函数
1.求字持串的长度LENGTH 您可用LENGTH函数求字符串的长度。LENGTH返回一个数值。该值等于参数中的字符个数。 例：使用LENGTH函数 SQL＞select Last_Name, length(Last_Name) from customer order by LastName; 2.使用SUBSTR函数从字符串中提取子串 语法： SUBSTR函数的语法如下： SUBSTR(string, string charcter, number of charcters) 变量定义如下： string为字符列或字符串表达式 string charcter为子串的起始位置 number of charcters为返回字符的个数c 例：说明了怎样使用SUBSTR函数取得教师的姓的前四个字符 SQL＞select last_Name, substr(Last_Name, 1, 4) from instector order by Last_Name 例：在SUBSTR函数中使用LENGTH函数（取后三个字符） 5Qt．＞select last_Name, substr(Last_Name, Length(Last_Name) - 2, 3) from instector order by Last_Name 3.在字符串中查找模式 例：使用LIKE运算符 SQL＞column description format a40 word_wrapped SQL＞column title format a35 SQL＞select Title, Description from Course where Description like '%thory%' or Description like '%theories%'; 4.替换字符串的一部分 经常遇到的数据操纵任务是在特定的列中将数据由一种模式转换成另一种模式。 假设您希望在Course表中改变课程说明，将说明中的字seminar用字discussion替代．那么您可用oracle提供的函数REPLACE，该函数使得某列的字符串能被另一字符串代替。 语法： REPLACE函数的语法如下： REPLACE(string, existion_string, [replacement_string]) 变量定义如下： string为字符表达式c existion_string为已存在的字符串。 replacement_string为用来替代的可选字符串。 例：使用REPLACE函数 显示了在Course表中如何使用REPLACE来改变课程名称(title)：首先使用查询显示当前课程名称，UPDATE语句中使用REPLACE函数将SEMINAR改变成
大学英语四级考试真题及答案(完整版)
大学英语四级考试真题及答案(绝对完整） Part I Writing (30 minutes) Directions: For this part, you are allowed 30 minute to write a short essay on the topic of students selecting their lectures. You should write at least 120 words following the outline given bellow: 1. 越来越多的博物馆免费对外开放的目的是什么？ 2. 也会带来一些问题 3. 你的看法？ Part II Reading Comprehension (Skimming and Scanning) (15 minutes)Directions: In this part, you will have 15 minutes to go over the passage quickly and answer the questions on Answer Sheet 1. For questions 1-7, choose the best answer from the four choices marked A),B),C) and D). For questions 8-10, complete the sentences with the information given in the passage. How Do You See Diversity? As a manager, Tiffany is responsible for interviewing applicants for some of the positions with her company .During one interview, she noticed that the candidate never made direct eye contact. She was puzzled and somewhat disappointed because she liked the individual otherwise. He had a perfect resume and gave good responses to her questions, but the fact that he never looked her in the eye said “untrustworthy,” so she decided to offer the job to her second choice. “It wasn’t until I attended a diversity workshop that I realized the person we passed over was the perfect person,” Tiffany confesses. What she hadn’t known at the time of the interview was that the candidate’s “different” behavior was simply a cultural misunderstanding . He was an Asian-American raised in a household where respect for those in authority was shown by averting(避开) your eyes. “I was just thrown off by the lack of ye contact; not realizing it was cultural,” Tiffany says. “I missed out ,but will not miss that opportunity again.” Many of us have had similar encounters with behaviors we perceive as different. As the world becomes smaller and our workplaces more diverse, it is becoming essential to expand our under-standing of others and to reexamine some of our false assumptions . Hire Advantage At a time when hiring qualified people is becoming more difficult ,employers who can eliminate invalid biases(偏爱) from the process have a distinct advantage .My company, Mindsets LLC ,helps organizations and individuals see their own blind spots . A real estate recruiter we worked with illustrates the positive difference such training can make .
月大学英语四级真题试卷及答案三套全
目录 2017 年12 月大学英语四级真题试题一(完整版) (1) 答案 (15) 2017 年12 月大学英语四级真题试题二(完整版) (15) 答案 (24) 2017 年12 月大学英语四级真题试题三(完整版) (24) 答案 (34) 2017 年12 月大学英语四级真题试题一(完整版) Part I Writing (25 minutes) (请于正式开考后半小时内完成该部分，之后将进行听力考试)? Directions:For this part, you are allowed 30 minutes to write an a short easy on how to besthandle the relationship between doctors and patients. You should write at least 120words but no more than 180 words. Part II Listening Comprehension (30 minutes) Section A Directions:In this section, you will hear three news reports. At the end of each news report, you will hear two or three questions. Both the news report and questions will be spoken only once. After you hear questions, you must choose the best answer from the four choices marked A), B), C) and D). Then mark the corresponding letter onAnswer Sheet 1 with a single line through the centre. 注意：此部分试题请在答题卡1 上作答。 Questions 1 to 2 are based on the new reportyou have just heard. 1.A)Her grandfather. B)Her grandfather.
Python语句、函数与方法的使用技巧总结
Python语句、函数与方法的使用技巧总结 显示有限的接口到外部 当发布python第三方package时，并不希望代码中所有的函数或者class可以被外部import，在__init__.py中添加__all__属性，该list中填写可以import 的类或者函数名，可以起到限制的import的作用，防止外部import其他函数或者类。 #!/usr/bin/env python # -*- coding: utf-8 -*- from base import APIBase from client import Client from decorator import interface, export, stream from server import Server from storage import Storage from util import (LogFormatter, disable_logging_to_stderr, enable_logging_to_kids, info) __all__ = ['APIBase', 'Client', 'LogFormatter', 'Server', 'Storage', 'disable_logging_to_stderr', 'enable_logging_to_kids', 'export', 'info', 'interface', 'stream'] with的魔力
with语句需要支持上下文管理协议的对象，上下文管理协议包含__enter__和__exit__两个方法。with语句建立运行时上下文需要通过这两个方法执行进入和退出操作。 其中上下文表达式是跟在with之后的表达式，该表达式返回一个上下文管理对象。 # 常见with使用场景 with open("test.txt", "r") as my_file: # 注意, 是__enter__()方法的返回值赋值给了my_file, for line in my_file: print line 知道具体原理，我们可以自定义支持上下文管理协议的类，类中实现__enter__和__exit__方法。 #!/usr/bin/env python # -*- coding: utf-8 -*- class MyWith(object): def __init__(self): print "__init__ method" def __enter__(self):
英语四级真题及答案
2017年6月英语四级真题 作文一： For this part,you are allowed 30 minutes to write a short essay based on the picture below. You should start your essay with a brief account of the impact of the Internet on the way people communicate and then explain whether electronic communication can replace face-to-face contact.You should write at least 120 words but no more than 180 words. “Dear Andy-How are you? Your mother and I are fine.We both miss you and hope you are doing well.We look forward to seeing you again the nest time your computer crashes and you come down-stairs for something to eat,Love,Mom and Dad.” 作文二： For this part,you are allowed 30 minutes to write a short essay based on the picture below. You should start your essay with a brief account of the impact of the Internet on learning and then explain why doesn’t simply mean learning to obtain information. You should write at least 120 words but no more than 180 words.
12月大学英语四级真题及答案汇总
2011年12月大学英语四级真题及答案汇总 一、写作部分 For this part, you are allowed 30 minutes to write a shortessay entitled Nothing Succeeds Without a Strong Will by commentingon the humorous saying, "Quitting smoking is the easiest thing inthe world. I've done it hundreds of times." You should write atleast 120 words but no more than 180 words。 Nothing Succeeds Without aStrong Will No great work can be performedwithout will. We envy famous men and imagine that fame was due tosome trick of luck. But when we know their histories, we find thatit is long years of will and constant effort that have broughtabout their success. Just as we can’t reach the top of a mountainwithout climbing, we can’t achieve success without will。 The modern society providespeople with more opportunities than before, and there are storieswhich tell us the possibility of becoming successful overnight.Actually that is not the case. Before these people becomesuccessful, a lot of hard work has been done, unnoticed mostly.What we usually see is the result, but what we ignore is a longprocess of struggling forward and wrestling with internal orexternal obstacles. Take “quitting
函数的极大值和极小值
4.3.2 函数的极大值和极小值 教学目标： 1.理解极大值、极小值的概念； 2.能够运用判别极大值、极小值的方法来求函数的极值； 3.掌握求可导函数的极值的步骤； 教学重点：极大、极小值的概念和判别方法，以及求可导函数的极值的步骤. 教学难点：对极大、极小值概念的理解及求可导函数的极值的步骤. 教学过程： 一．创设情景 观察图3.3-8，我们发现，t a =时，高台跳水运动员距水面高度最大．那么，函数()h t 在此点的导数是多少呢？此点附近的图像有什么特点？相应地，导数的符号有什么变化规律？ 放大t a =附近函数()h t 的图像，如图3.3-9．可以看出()h a '；在t a =，当t a <时，函数()h t 单调递增，()0h t '>；当t a >时，函数()h t 单调递减，()0h t '<；这就说明，在t a =附近，函数值先增（t a <，()0h t '>）后减（t a >，()0h t '<）．这样，当t 在a 的附近从小到大经过a 时，()h t '先正后负，且()h t '连续变化，于是有()0h a '=． 对于一般的函数()y f x =，是否也有这样的性质呢？ 附：对极大、极小值概念的理解，可以结合图象进行说明.并且要说明函数的极值是就函数在某一点附近的小区间而言的. 从图象观察得出，判别极大、极小值的方法.判断极值点的关键是这点两侧的导数异号 二．新课讲授 1．问题：图 3.3-1（1），它表示跳水运动中高度h 随时间t 变化的函数 2() 4.9 6.510 h t t t =-++的图像，图3.3-1（2）表示高台跳水运动员的速度v 随时间t 变化的函数'()()9.8 6.5v t h t t ==-+的图像． 运动员从起跳到最高点，以及从最高点到入水这两段时间的运动状态有什么区别？ 通过观察图像，我们可以发现： （1） 运动员从起点到最高点，离水面的高度h 随时间t 的增加而增加，即()h t 是 增函数．相应地，' ()()0v t h t =>． （2） 从最高点到入水，运动员离水面的高度h 随时间t 的增加而减少，即()h t 是 减函数．相应地，'()()0v t h t =<． 2．函数的单调性与导数的关系 观察下面函数的图像，探讨函数的单调性与其导数正负的关系． 如图 3.3-3，导数'0()f x 表示函数()f x 在点00(,)x y 处的切线的斜率．在0x x =处，
大学英语四级真题及答案.doc
大学英语四级真题及答案( 多套题及翻译） CET4 Part I Writing (30 minutes) Directions: For this part, you are allowed 30 minutes to write a short essay on the following topic. You should write at least 120 words but no more than 180 words. 目一：Suppose a foreign friend of yours is coming to visit your campus, what is the most interesting place you would like to take him/her to see and why? 假你的一位外国朋友来参你的校园，你最感趣的地方想他/ 她去看 ?什么 ? 目二：Suppose a foreign friend of yours is coming to visit your hometown, what is the most interesting place you would like to take him/her to see and why? 假你的一位外国朋友来参你的家，你最感趣的地方想他/ 她去看 ?什么 ? 目三：Suppose a foreign friend of yours is coming to visit China, what is the most interesting place you would like to take him/her to see and why? 假你的一位外国朋友来参中国，你最感趣的地方想他/ 她去看 ?什么 ? Part II Listening Comprehension (30 minutes) Section A Directions: In this section, you will hear 8 short conversations and 2 long conversations. At the end of each conversation, one or more questions will be asked about what was said. Both the conversation and the questions will be spoken only once. After each question there will be a pause. During the pause, you must read the four choices marked A), B), C) and D), and decide which is the best answer. Then mark the corresponding letter on Answer Sheet 1 with a single line through the centre. 注意：此部分在答卡 1 上作答。 1.A. See a doctor about her strained shoulder a ladder to help her reach the tea. the cupboard with a new one. the tea on a lower shelf next time. 1. W: I can’t seem to reach the tea at the back of the cupboard 。 M: Oh? Why don’t you use the ladder? You might strain your shoulder 。 Q: What does the man suggest the woman do? 2. A. At Mary Johnson’s B. In an exhibition hall C. At a painter’s studio. D. Outside an art gallery. 2. W: Since it’s raining so hard, let’s go and see the new exhibits 。 M: That ’s a good idea. Mary Johnson is one of my favorite painters 。 Q: Where does the conversation most probably take place?
一次函数表达式与坐标
一次函数表达式与坐标（讲义） 一、 知识点睛 1. 一次函数表达式 直线（函数图象） 坐标 点 2. 坐标系中处理问题的原则 （1）坐标转线段长、线段长转坐标； （2）作横平竖直的线． 二、 精讲精练 1. 若点M 在函数y =2x -1的图象上，则点M 的坐标可能是（ ） A ．(-1，0) B ．(0，-l) C ．(1，-1) D ．(2，4) 2. 若直线y =2x +1经过点(m +2，1-m )，则m =______． 3. 一次函数y =-2x +3与x 轴交于点_____，与y 轴交于点_____． 4. 在一次函数2 1 21+=x y 的图象上，与y 轴距离等于1的点的坐标为 __________________． 5. 若点(3，-4)在正比例函数y =kx 的图象上，那么这个函数的解析式为（ ） A ．43y x = B ．43y x =- C ．34y x = D ．3 4 y x =- 6. 若正比例函数的图象经过点(-1，2)，则这个图象必经过点（ ） A ．(1，2) B ．(-1，-2) C ．(2，-1) D ．(1，-2) 7. 已知某个一次函数的图象过点A (-2，0)，B (0，4)，求这个函数的表达式. 8. 已知某个一次函数的图象过点A (3，0)，B (0，-2)，求这个函数的表达式. 9. 如图，直线l 是一次函数y =kx +b 的图象，填空： （1）k =______，b =______； （2）当x =4时，y =______； （3）当y =2时，x =______．
10. 已知y 是x 的一次函数，下表给出了部分对应值，则m 的值是________． 11. 一次函数y=kx +3的图象经过点A (1，2)，则其解析式为____________. 12. 若一次函数y=2x+b 的图象经过点A (-1，1)，则b =______，该函数图象经过 点B (1，___)和点C (_____，0)． 13. 若直线y =kx +b 平行于直线y =3x +4，且过点(1，-2)，则将y =kx+b 向下平移3 个单位得到的直线是_____________． 14. 在同一平面直角坐标系中，若一次函数y =-x +3与y =3x -5的图象交于点M ， 则点M 的坐标为（ ） A ．(-1，4) B ．(-1，2) C ．(2，-1) D ．(2，1) 15. 直线y =2x+b 经过直线y=x -2与直线y =3x +4的交点，则b 的值为（ ） A ．-11 B ．-1 C ．1 D ．6 16. 当b=______时，直线y =2x +b 与y =3x -4的交点在x 轴上． 17. 一次函数y =kx +3的图象与坐标轴的两个交点间的距离为5，则k 的值为 __________． 18. 直线y =3x -1与两坐标轴围成的三角形的面积为_________． 19. 已知直线y =kx +b 经过(5，0)，且与坐标轴所围成的三角形的面积为20，则 该直线的表达式为______________________． 20. 点A ，B ，C ，D 的坐标如图所示，求直线AB 与直线CD 的交点E 的坐标． 21. 如图，已知直线l 1：y =2x +3，直线l 2：y =-x +5，直线l 1，l 2分别交 x 轴于B ， C 两点，l 1，l 2相交于点A ． （1）求A ，B ，C 三点坐标； （2）S △ABC =________．
2020年精品-大学英语四级真题及答案
未得到监考老师指令前，不得翻阅该试题册! Part 1 Writing (30 minutes) (请于正式开考后半小时内完成该部分，之后将进行听力考试) Directions: For this part, you are allowed 30 minutes to write an essay based on the picture below. You should start your essay with a brief description of the picture and them comment on this kind of modern life. You should write at least 120 words but no more than 180 words. THIS MODERN LIFE: WORK HOME PLAY SLEEP 请用黑色签字笔在答题卡1指定区域作答作文题，在试题册上的作答无效。
Part II Listening Comprehension (30minutes) Section A Directions: In this section, you will bear 8 short conversations and 2 long conversations. At the end of each conversation, one or more questions will be asked about what was said. Both the conversation and the questions will be spoken only once. After each questions there will be a pause. During the pause, you must read the four choices marked A), B),C) and D), and decide which is the best answer. Then mark the corresponding letter on Answer sheet 1 with a single line through the center. 注意：此部分试题请在答题卡1上作答 1. A) He is pleased to sit on the committee C) He will tell the woman his decision later B) He is willing to offer the woman a hand D) He would like to become a clu b member 2. A) Their planned trip to Vancouver is obviously overpriced B) They should borrow a guide book instead of buying one C ) The guide books in the library have the latest information D) The library can help order guide books about Vancouver 3. A) He regrets having taken the history course B) He finds little interests in history books C) He has trouble finishing his reading assignments D) He has difficulty in writing the weekly book report 4. A) The man had better choose another restaurant B) The new restaurant is a perfect place for dating C) The new restaurant caught her fancy immediately D) The man has good taste in choosing the restaurant 5. A) He has been looking forward to sping C)He will clean the woman?s boots f or spring C) He has been waiting for the winter sale D) He will help the woman put things away 6. A) At a tailor?s C) In a cloth store B) At Bob?s home D) In a theatre 7. A) His guests favors Tibetan drinks C) Mineral water is good for health B) His water is quite extraordinary D) Plain water will serve the purpose