text:
# Part IITutorial Example: Creating a Simple Server

### 3 Introduction

This part of the document is a tutorial example which describes how to create a simple ACL server. Example files are provided which illustrate the procedure. Firstly, however, the basics of using an ACL server to query a catalogue are reviewed.

### 4 Basics of Querying Remote Catalogues

The basics of querying a catalogue are that some criterion is specified, all the rows in the catalogue are examined and those which satisfy the criterion are returned as the list of selected rows. Some criteria might be:

• stars whose Right Ascension lies in the range $13h\phantom{\rule{0.3em}{0ex}}30\text{}m\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}.\text{}0$ to $14h\phantom{\rule{0.3em}{0ex}}00\text{}m\phantom{\rule{0.3em}{0ex}}\phantom{\rule{0.3em}{0ex}}.\text{}0$,
• stars brighter than ${m}_{v}=13.0$,
• stars with a B-V colour greater than 0.2.

However, a very common sort of search on astronomical catalogues is the so-called ‘circular area search’ or ‘cone search’. Virtually all astronomical catalogues contain celestial coordinates, in practice Right Ascension and Declination for some equinox and epoch. In a circular area search the central coordinates and angular radius are specified. All the objects in the catalogue which are less than this angular radius from the central coordinates are selected. That is, the circular area search finds all the objects in the catalogue within a given circular patch of sky.

It is usual for ACL servers to a support a circular area search and often this may be the only type of search provided. The full form of an ACL circular area search is slightly more general, with both an inner and outer radius specified, so that objects inside an annulus rather than a circle are selected. (The ‘traditional’ circular area search corresponds to setting the inner radius to zero.)

The catalogue being accessed will doubtless have other columns as well as the Right Ascension and Declination, and the ACL server may permit ‘range’ searches on some of these columns. In a range search minimum and maximum values are specified for a column and a row is selected if its value for the column falls within the given range. Any range searches specified are combined with each other and with the circular area search using a ‘logical and’. That is, for example, the objects selected would correspond to those which are both in a given area of sky and in a given magnitude range. Though this mechanism allows powerful queries to be made it still provides only a subset of all the conceivable types of queries.

Before starting work on an ACL server for a catalogue, you need to decide two things.

(1)
Are circular area searches to be supported (the answer is almost certainly yes)?
(2)
On which, if any, additional columns are range searches to be supported?

In order to implement the server you need to provide two things:

(1)
the server itself,
(2)
an entry for the server in an ACL ‘configuration file’.

An ACL configuration file defines the list of catalogues which a client, such as GAIA or SkyCat, currently knows about. It has an entry for each catalogue. The entry specifies details of the catalogue which the client needs to know: the URL of its server, the types of queries that it supports, the name by which it is to be described to the user etc.

### 5 Obtaining Example Files

Some simple examples of server scripts and a configuration file are provided with this document. Subsequent sections of the tutorial will describe these files and explain how to install them. You may also find them useful as templates for developing your own servers and configuration files. The files can be obtained in two different ways.

• On Starlink systems they should be present in directory:

/star/examples/ssn75

• Copies can be obtained by anonymous ftp from Edinburgh. The details are:
 Anonymous ftp to: ftp.roe.ac.uk Directory: /pub/acd/misc File: ssn75_examples.tar

The file is an uncompressed tar archive (it is only 52 Kb in size). Set ftp to ‘binary’ mode to retrieve it.

The important files used in the tutorial are:

simpleserver.cgi
a simple server script,
secondserver.cgi
a second, slightly more complicated, server script,
genfield.c
a program to generate the list of stars returned by the servers,
simpleconfig.cfg
a configuration file including the two example servers.
checkcfg
a script for checking configuration files.

File 0README.LIS gives a complete list. You will probably find it useful to print out copies of the files and have them to hand as you work through the examples. Copies of the servers are installed at Edinburgh, so the URLs given in the examples should work, though you will be accessing the Edinburgh versions rather than your own copies.

### 6 Creating a Server

An ACL server is a Perl script which accepts a query in a standard format, searches the corresponding catalogue to find the objects which satisfy the query and returns them to the remote client. The server simpleserver.cgi supplied with this document is more-or-less the simplest practical server, but it illustrates the structure that they usually have. You will find it helpful to have a copy to hand as you read through this section. simpleserver.cgi supports only circular area searches in which a central Right Ascension and Declination and an angular radius are specified. Because it is provided as an example it generates and returns an artificial list of stars, centred on, and scaled to fit, the specified area, rather than searching a real catalogue. The overall structure of simpleserver.cgi is:

obtain the query string
parse the query string to obtain the central coordinates and radius
generate the list of stars to fit in this field
(a real server would search a catalogue instead)
return the results to the client

The comments in the source code should make the detailed working obvious. However, the following notes about the query string and results returned might be useful.

(1)
If a CGI gateway is implemented as a Perl script the query string appears in the variable $ENV{’QUERY_STRING’}. In simpleserver.cgi the query is copied into a local variable by the line:$query = $ENV{’QUERY_STRING’}; (2) In simpleserver.cgi the query string has the format: ra=xxx&dec=yyy&radius=zzz For example: ra=10:30:00&dec=-30:30.0&radius=3 where ra=, dec= and radius= have their obvious meanings. When you set up the entry for the server in the configuration file (see Section 7, below) you have considerable latitude over this format. However, the one used by simpleserver.cgi is a common one, and is as good as any. simpleserver.cgi supports only circular area searches; if additional types of search were supported then the query string would contain additional parameters. (3) The formats and units required for the parameters are as follows: Right Ascension sexagesimal or decimal hours, Declination sexagesimal or decimal degrees, Radius decimal minutes of arc. If a sexagesimal value is entered then a colon (‘:’) should be used as a separator. The Right Ascension and Declination should be for equinox and epoch J2000. The server must accept values in these units and formats because typically the client will present the same recipe and information to the user when requesting input for any of the various catalogues available to it. #### 6.2 Results returned (1) The first line of information returned by the server should always be the MIME type. In simpleserver.cgi it is written by the line: { print "Content-type: text/plain\n\n\n"; The MIME type is not part of the table of results, but rather is used by the client or Web browser to interpret the format of the data which follows. (2) The list of selected objects are returned to the client as a stream of ASCII characters. The list is written in the Tab-Separated Table (TST) format (see Section 11). (3) The Perl script should simply write the results to standard output (whence it will be automatically forwarded to the remote client). In simpleserver.cgi the lines:$tst = ‘$queryExe$ra $dec$radius‘;
print "$tst"; invoke program genfield (variable$queryExe has previously been set to contain the name and directory specification of the executable for genfield) to generate the star list, copy the list the to variable $tst and then write the contents of$tst to standard output. (Hint: Perl has several mechanisms for invoking processes and directing their output to standard output; I found the one described to be the most suitable for use in a CGI script.)

(4)
The last line written to standard output should be:

print "[EOD]\n";

The string ‘[EOD]’ informs the client that the server has finished sending data.

#### 6.3 Installing and testing the server

The procedures for installing CGI scripts vary at different sites; your system manager should be able to advise on arrangements at your site. However, to install simpleserver.cgi you need to follow at least the following steps.

(1)
Copy files simpleserver.cgi and genfield.c to a suitable directory (there are likely to be restrictions on which directories can contain CGI scripts; see your system manager).
(2)
Compile program genfield.c and name the executable genfield. genfield.c is a standard (and simple) C program; any C compiler should be able to handle it.
(3)
Edit file simpleserver.cgi. Locate the line:

$queryExe = "/star/examples/ssn75/genfield"; which is towards the top of the script and change it to correspond to whichever directory you have put the files in. (4) Check with your system manager whether there are any other local requirements for running CGI scripts. (5) You are now ready to test the server. The tests are best conducted from a normal Web browser, such as netscape. Start the browser and enter a URL similar to: http://www.roe.ac.uk/~acd/cgi-bin/simpleserver.cgi?ra=10.0&dec=30.0&radius=3 This string comprises the normal URL for the CGI script, followed by a ‘?’, followed by the query. This format is the normal syntax for invoking CGI scripts and passing queries to them. To invoke your version of the server you would substitute the appropriate URL in the example above. Typing in the example exactly as given should invoke a version of the server running in Edinburgh. If all is working correctly the browser should display a table similar to the one in Figure 1. If the server fails then your Web server probably maintains error logs which might contain useful diagnostics; your system manager should know where these logs are kept. Example Star Field. #column-units: DEGREES DEGREES Magnitudes #column-types: CHAR*8 DOUBLE DOUBLE REAL #column-formats: A8 F12.6 F12.6 F6.2 Id RA DEC mag -- -- --- --- Star 1 150.026667 30.050000 0.580000 Star 2 149.968333 29.961667 0.120000 Star 3 149.983333 30.041667 1.640000 Star 4 149.993333 30.005000 2.210000 Star 5 150.000000 30.000000 1.700000 Star 6 150.006667 29.996667 1.790000 Star 7 149.983333 29.993333 3.380000 Star 8 150.015000 29.951667 4.130000 [EOD] Figure 1: The table of values returned by the ACL server simpleserver.cgi. #### 6.4 Modifying the server Other servers are likely to be similar to simpleserver.cgi. To modify it to access your own catalogue you would replace the invocation of program getfield with an invocation of a program which searched your catalogue or DBMS. simpleserver.cgi is more-or-less the simplest practical server, and is provided as an example. Additional useful features in a server include: copying the queries to a log file (so that you can monitor usage) and copying error messages to a second log file (as diagnostics in case of misadventure). Another server, secondserver.cgi, which incorporates these features, is supplied with this document. To install it, follow the same procedure as for simpleserver.cgi, except that the lines towards the top of the script which need to be modified are:$queryExe = "/star/examples/ssn75/genfield";
$logDir = "/star/examples/ssn75/examplelogs"; When developing a server it is often useful to comment out the line:$query = $ENV{’QUERY_STRING’}; and un-comment the line: #$query = "ra=10:30:00&dec=-30:30.0&radius=3";

so that the script has a query ‘hard-wired’. It can now be run directly from the command line rather than be invoked via a Web browser. This trick often makes debugging scripts a lot easier.

Both the query and error log files written by secondserver.cgi are simple text files. Note, however, that file query.TXT, which is supplied with the examples, allows the query log to be accessed by CURSA[3] as an STL (Small Text List) format catalogue. Once the query log becomes large you might find it more convenient to examine it with the CURSA catalogue browser xcatview rather than Unix commands such as cat and more.

### 7 Creating a Configuration File

The configuration file used by GAIA etc. mediates interaction between the client and server. It is an ASCII text file containing details for each of a list of catalogues. GAIA (or whatever) reads the file and the catalogues listed in it become the ones that GAIA knows about. The details supplied for each catalogue are things like: its URL, the type of queries supported, the name that will be used to describe it to users etc. The entry for a typical simple catalogue looks something like:

serv_type:      catalog
long_name:      Simple example server.
short_name:     simple@roe
url:            http://www.roe.ac.uk/~acd/cgi-bin/simpleserver.cgi?ra=...
symbol:         mag circle 3

This entry is taken from simpleconfig.cfg, the example configuration file supplied with this document, though the url entry has been truncated. By convention configuration files have file type ‘.cfg’. The purposes of the various items are as follows.

serv_type:
is the type of the server. For a straightforward catalogue the value required is ‘catalog’. Other values are possible, though you will probably rarely use them.
long_name:
a one-line name or short description of the catalogue. It will be presented to the user to allow him to identify the catalogue.
short_name:
a short name for the catalogue. Conventionally it has the form:

catalogue@institution

where catalogue is an abbreviation for the catalogue and institution a standardised abbreviation for the institution where the on-line version is located. By convention institution has three or four characters.

url:
the URL used to access the server. Following the usual conventions for a CGI gateway it consists of the URL corresponding to the script which constitutes the server, followed by a ‘?’ and then a string defining the query passed to the server (see Section 7.1).
symbol:
specifies how objects are to be plotted (see Section 10.6).

There are various other optional items which can be included. They are described in Section 10.

#### 7.1 URL query

The string appended to the server URL in the configuration file and which defines the type of queries supported by the catalogue has a format something like:

It consists of simple characters and ‘tokens’. The tokens start with a ‘%’ character. When GAIA makes a query the tokens are replaced with values which correspond to the individual query and the resulting string is sent to the server. For example, tokens in the above string might be susbstituted to yield:

Obviously the format of the query string appended to the URL in the configuration file must correspond to that expected by the server. Various standard tokens can be included in the query string. Some common ones are:

%ra
Right Ascension,
%dec
Declination,
%r1
%r2
%n
maximum number of objects to return.

For a complete list see Section 10.

#### 7.2 Installing and testing the configuration file

Installing and testing the configuration file should be quite straightforward. The servers
simpleserver.cgi and secondserver.cgi should be installed (see Section 6, above). Then proceed as follows.

(1)
Edit the configuration file and change the URLs for the servers simple@roe and second@roe to correspond to wherever you have installed the servers.
(2)
A Perl script to check a configuration file for errors is included with the example files for this document. To check that you have not introduced any errors whilst editing the example configuration file type:

/star/examples/ssn75/checkcfg   simpleconfig.cfg

(If the example files are not in their standard location on a Starlink system then obviously you need to alter the directory specification accordingly. Also, on non-Starlink systems you might need to edit the first line of checkcfg to correspond to wherever Perl is installed on your system.) If the configuration file is valid then checkcfg will report:

Configuration file parsed successfully.

Conversely, if it contains errors then messages describing the problems will be reported. checkcfg is described in Section 10.7.

(3)
Start GAIA and test the server. To import the configuration file into GAIA click on the Data-Servers button on the right hand side of the main menu bar and choose the Browse Catalog Directories option. A window showing the catalogues available should appear. Click on the File button at the left of its top menu bar and choose the Load Config file… option. A window allowing you to select the required file should then appear.

Once the configuration file has been loaded you can choose from amongst its catalogues and make selections in the normal fashion. If you make a selection from the simple example server a list of objects similar to Figure 1 should be returned.

#### 7.3 Modifying the configuration file

When you create a new server you need to create an entry for it in your configuration file. If the server is just a simple variation of simpleserver.cgi or secondserver.cgi and only supports circular area queries then just duplicate the entry for simple@roe and change long_name, short_name and url to correspond to your server.

Additional modifications can be made as required. The following section gives some examples and the options are documented in Section 10. Remember that script checkcfg (see Section 10.7) is available for checking configuration files.

### 8 Carrying On

This section introduces a few additional features that are often required in servers and configuration files.

#### 8.1 Multiple catalogue servers

simpleserver.cgi can access only a single catalogue. Often you may want to write a server which can access each of several catalogues. In this case your configuration file must contain an entry for each catalogue, not each server. An additional parameter, whose value identifies the catalogue, is added to the query. The server parses this parameter to identify the catalogue required. You can decide the syntax and values of this parameter, though the configuration file and server must agree.

For example, suppose that you are writing a server which will provide access to the SAO, PPM and Hipparcos astrometric catalogues. You might invent a parameter called ‘catalogue’ whose value identifies the catalogue. Your configuration file would then have three entries like:

serv_type:  catalog
long_name:  SAO (Smithsonian Astrophysical Observatory) catalog
short_name: sao@roe
url:        http://www.roe.ac.uk/~acd/cgi-bin/ast.cgi?catalogue=sao&ra=%ra&dec=...
symbol:     mag square 3

serv_type:  catalog
long_name:  PPM (Positions and Proper Motions) catalogue
short_name: ppm@roe
url:        http://www.roe.ac.uk/~acd/cgi-bin/ast.cgi?catalogue=ppm&ra=%ra&dec=...
symbol:     mag square 3

serv_type:  catalog
long_name:  Hipparcos catalogue
short_name: sao@roe
url:        http://www.roe.ac.uk/~acd/cgi-bin/ast.cgi?catalogue=hipparcos&ra=%ra&dec=...
symbol:     mag square 3

The server would be written to parse the value of catalogue and then search the catalogue indicated.

#### 8.2 Providing range queries

As well as selecting objects in a circular area of sky it is possible to further restrict the objects selected to only those for which the values of some column lie within a given range. Suppose selections from an optical catalogue were to be optionally restricted to also lie within a specified range of magnitudes and the column of magnitudes was named mag. To provide this facility for a catalogue its entry in the configuration file should be include the keyword search_cols and the query part of its url keyword should include the token %cond.

(1)
The syntax of the search_cols keyword is:

search_cols:column-name minimum-prompt maximum-prompt

For example:

search_cols: mag "Bright limit" "Faint limit"

column-name is the name of the column. The client uses minimum-prompt and maximum-prompt as prompts when soliciting the extrema of the required range from the user. (Note that because the example column is a magnitude the “Bright limit" corresponds to the smallest numerical value and the “Faint limit" to the largest.)

(2)
The %cond token is added to the query part of the url keyword to supply details of the range query. Such a query string might look like:

The syntax of the values substituted into the %cond string is:

column-name =minimum-value,maximum-value

For example, if a range of first to second magnitude had been specified for column mag then %cond would translate to:

mag=1.0,2.0

The server that parses the query must interpret this string and ensure that the range selection specified is applied.

See Section 10.5 for further details.

For a directory entry the serv_type should be ‘directory’ and the url should be the URL of the destination configuration file. long_name and short_name have their usual meaning. Other options are unlikely to be required. An example might be:


text:
# Why would members of the public ever choose to take slower than light interstellar travel?

Another question on this site deals with the question of interstellar trade without faster than light travel. I'd like inspiration for a related but more generic question. Why would people choose to take an expensive and years long interstellar journey in a world allowing ubiquitous fast, but sub-luminal travel?

Some useful scene setting information:

• Fancy soft science fiction engines allow small (<100 person) space ships to travel at 0.99c in intergalactic space.
• This travel can either be conscious, costing about 5 years salary per light year for an average worker, or in a sleeper state in which metabolic processes are slowed for two years salary per light year.
• Larger cheap/government sponsored generational & sleeper ships have existed for a couple of centuries and have been used to terraform and colonise a region of space near the home world.
• No alien species are known to exist.
• To be clear, do you mean intergalactic or interstellar? To travel to the Andromeda galaxy (a "close" galaxy) would take 2.5 million years at subluminal speeds – Kys Mar 4 '16 at 18:01
• Ooops. Lets fix that. – origimbo Mar 4 '16 at 18:02
• "Why would people choose to take an expensive and years long interstellar journey in a world allowing ubiquitous fast, but sub-luminal travel?" I'm not sure I understand. Are you saying the world has FTL or not? Because even at 0.99c that "ubiquitous fast, but sub-luminal travel" will still take years (in Earth's reference frame) to reach the nearest star. Is the choice between FTL and 0.99c? Or between 0.99c and something even slower? – Schwern Mar 4 '16 at 18:32
• No FTL, just tricks with acceleration. The fundamental question is "is there a justifiable reason for normal(ish) people to take the time out of their lives to make such trips. – origimbo Mar 4 '16 at 18:36
• Do note that if it's perfectly okay if no normal member of public wouldn't choose so - if only one-in-a-ten-thousand weirdos are eager to do it, it's completely enough for most intents and purposes. – Peteris Mar 4 '16 at 21:42

I think this question really boils down to 'why would someone pay money to go somewhere?' And the answer to this question, in almost any case, is twofold:

1) - Get away from bad things where you are. Maybe you've made a lot of money by swindling a lot of important people, or perhaps you've profited from a war that now threatens to destroy the planet you live on. Either way, if it'll cost more to you to stay than it would to leave, then you're going to choose to leave. Since the cost of travel is so high and you probably won't be coming back, I'd say for most people, the cost of staying would have to be their life, or the lives of people they care about. Essentially, refugees.

2) - Go to good things where you aren't. Sometimes, the planet you're living on just isn't all that great. Maybe you're a painter, and the best painting teachers in the galaxy all live on the planet next to yours, or you're an entrepreneur on a planet with no resources. Or maybe you're the most brilliant scientist in your field, and someone wants to pay for your trip to their lab. In these and similar cases, your life probably won't be in danger, but there's got to be some pretty tantalizing rewards at the end of the road to leave everything behind and put down so much money.

There's also a third option:

3) - You're a decadent rich person looking to show off. How do you convince people to eat fish eggs and wear shiny rocks? You charge them a lot of money for it. In high-society parties, the rich people who can show off their rich-ness the best win. Even today, people love to tell everyone about the beautiful corners of the world they've traveled to; now imagine these corners are on different planets, and a vastly smaller percentage of people will have been able to visit them.

One might choose to travel at .99c to take advantage of the significant degree of relativistic time dilation associated with that speed. If nothing else, it's an effective version of one-way time travel. It might be tempting to some to see what things are like a thousand years in the future.

• Also remember that the time dilation means the person travelling experiences much less time passing. That means that even though the people back home think it takes say 4 years for the ship to reach Alpha Centauri, to the person travelling it could be only a few weeks. Depending on acceleration, of course. See the Physics site for relevant math. – jamesqf Mar 4 '16 at 18:24
• The relativistic time dilation makes a 1 year journey about 7 years "real" time. Not necessarily as much as you would expect. – Lacklub Mar 4 '16 at 18:34
• This is a plot element of The Forever War where they use it as a human time capsule. And Wolfram Alpha will do the time dilation math for you. – Schwern Mar 4 '16 at 18:35
• The time dilation would become more significant if they got even closer to c. For every 2 9's added to c, the time dialation grows by 10. So while .99c may not be that much, .999999c is a big leap forward. So it could be reasonable if OP's world isn't tied to just 2 9's. – Lawtonfogle Mar 4 '16 at 21:26
• @Lacklub: Well, that's relative, isn't it? (Pun intended, of course :-)) For the traveller, the time s/he experiences is what's "real". – jamesqf Mar 5 '16 at 4:59

This travel can either be conscious, costing about 5 years salary per light year for an average worker, or in a sleeper state in which metabolic processes are slowed for two years salary per light year.

This is the kicker right here, price. Getting to the closest star, at 4.3 ly, would take 21.5 years salary awake, or 8.6 years asleep. For the US the average wage is about $45,000 so a trip to the next star over is equivalent to buying a nice house! In cash! If the economy is anything like it is now, the overwhelming majority of people could not amass the money to afford the trip. Average wage is deceptive, the majority of people make far, far less. The median (the point where half the people make more, half make less) US per-capita income is$15,500. To afford a trip, most people would have to go heavily into debt. Perhaps indentured servitude would return.

The price might be comparable to a 19th century person selling all their possessions and traveling to America from Europe, or to the American West, for a new life.

BTW, clever to do the pricing in light years traveled. If it were by time alone there could be a relativistic pricing problem.

Why would people choose to take an expensive and years long interstellar journey in a world allowing ubiquitous fast, but sub-luminal travel?

Even at 0.99c it takes years (in the frame of the place you departed from) to reach even the next star. For Earth, Alpha Centauri is the next star over at 4.3 light years. From Earth's perspective the ship will take 4.3 years (discounting time to accelerate), while from the traveler's perspective it will take 0.6 years (7x time dilation at 0.99c).

That is the problem with this question. It appears to want to compare "an expensive and years long interstellar journey" to "ubiquitous fast, but sub-luminal travel". But as shown above, the 0.99c journey is both expensive and years long.

So what is the alternative means of travel?

At those prices they are unlikely to, only the rich can afford it and the rich are unlikely to want to take the risk.

Initially it would done just by explorers and adventurers.

If some tempting places to settle were found though then for some people the chance of a fresh start is going to seem appealing. Just think of how many months or even years of travel people used to put in to get from Europe to parts of the USA or even Australia.

The problem is that people willing to do that normally are not the super wealthy, and you've priced it to the point that only the super wealthy can afford it. You really need to drop the price if you want it to become more regular.

Given the high cost of travel, I suspect that "indentured servitude" is the real answer. Since the average person cannot realistically come up with the money to travel to another star system, and since the price is per LY travelled, going beyond Alpha Centauri becomes very expensive indeed; Barnard's star is 6LY, 40 Eridani A is 16LY away and Vega is 25LY away. These are the nearest stars, globular clusters are tens of thousands of LY away at the far end.

However, given there is interstellar travel and presumably interstellar colonies, then sharp operators in the colonies will recognize the need for skills, labour and to broaden and deepen the local gene pool. You might be enticed to sign up for a trip to some distant star, but the promotor who is paying for this is going to:

a. Stick you in the freezer, and,

b. Have you on a long term contract where most of your wages pay for the ticket price plus interest.

This could be a win win for all concerned. You can remove yourself from a bad situation on the home planet, the new planet gets your skills and genes, and after a suitable period of time, you will be able to finish your contract and start afresh in the New World.

This is how many poor people came over to the 13 colonies of the Americas during the 1700's, and a lot of people considered it a good deal to take seven years indenture for the chance to live in the New World and have the ability to purchase land of your own after your indenture was done. While your starlight is quite costly, with the proper incentives in place, there will be a segment of the population which will still look at this as a good deal for them, and sign on the dotted line.

format: plain


text:
# 数学代写|密码学代写cryptography theory代考|CS6260

## 数学代写|密码学代写cryptography theory代考|Finding Suitable Primes

The prime number theorem says that in any given range of integers, primes are fairly common (inversely proportional to the number of digits). Since we can efficiently recognise primes, we can fairly quickly find large primes simply by choosing random large numbers until we find a prime.

By Requirement 2.5, we need a cyclic group such that the group order is divisible by a large prime. This means that we are not just looking for primes, we are looking for a prime $p$ such that $p-1$ is divisible by a large prime.
We can do this by first choosing a sufficiently large prime $\ell$ and then choosing random numbers $k$ until $2 k \ell+1$ is prime. In practice, this algorithm performs as well as a search for an arbitrary prime.

Example 2.19. Testing integers sequentially starting at 2000, we find that $\ell=$ 2003 is prime. We then test multiples starting with 101 and find that when $k=103$ the number $p=2 k \ell+1=412619$ is prime.

Sometimes, we want the $p-1$ to be twice a prime $\ell$. In this case, $p$ is called a safe prime and $\ell$ is called a Sophie-Germain prime. This time, the need for $\ell$ and $2 \ell+1$ to be prime simultaneously means that we need to look at many more candidates before we find a suitable prime. This will be slow, but there are techniques to speed up the search.

Example 2.20. Again, testing integers sequentially starting at 2003, we find that $\ell=2039$ is prime at the same time as $p=2 \ell+1=4079$.

Exercise $2.53$. About one third of all candidates will be divisible by 3 . Checking that a number is not divisible by 3 is much faster than using the primality testing algorithms from Section 2.3. Expand on this idea and explain how we can use so-called trial division by small primes to exclude most candidate primes before finally using the algorithms from Section $2.3$.

## 数学代写|密码学代写cryptography theory代考|Index Calculus

All of the algorithms from Section $2.2$ will work for $\mathbb{F}_p^*$. But it turns out that we can do very much better. We shall develop the ideas of index calculus in a general setting, and then show how the properties of prime fields give us a more efficient algorithm for computing discrete logarithms.

We begin with an observation about abstract cyclic groups, which is an extension of (2.1). Let $G$ be a cyclic group of order $n$. Let $g$ be some generator and let $x$ be a group element. Suppose we have $\nu$ pairs of integers $\left(r_1, t_1\right),\left(r_2, t_2\right), \ldots,\left(r_\nu, t_\nu\right)$ and integers $\alpha_1, \alpha_2, \ldots, \alpha_\nu$ (not all congruent to zero modulo $n$ ) such that
$$\prod_{i=1}^\nu\left(x^{t_i} g^{r_i}\right)^{\alpha_i}=1$$
This will give us the equation
$$x \sum_i \alpha_i t_i g^{\sum_i \alpha_i r_i}=1,$$
which is of the same form as (2.1). As long as $\sum_i \alpha_i t_i$ is invertible modulo $n$, we can recover $\log _g x$ from the equation using $2 \nu+2$ arithmetic operations $(\nu+1$ multiplications, $\nu$ additions and one inversion).
We first consider the case when the group order $n$ is prime.
Example 2.21. Consider the prime $p=1019$ with the elements $g=3$, generating a subgroup $G$ of $\mathbb{F}_p^*$ of order 509 . Let $x=11$.
With the relations
\begin{aligned} &y_1=g^{112} x^{239}=576 \quad y_2=g^{477} x^{274}=70 \quad y_3=g^{378} x^{248}=180 \ &y_4=g^{80} x^{66}=42 \quad y_5=g^{331} x^{488}=720 \ & \end{aligned}
and intègers $\alpha_1=145, \alpha_2=436, \alpha_3=72, \alpha_4=73$ and $\alpha_5=1$, wee get that
$$y_1^{145} x_2^{436} y_3^{72} y_4^{73} y_5=1$$

# 密码学代考

## 数学代写|密码学代写cryptography theory代考|Index Calculus

$$\prod_{i=1}^\nu\left(x^{t_i} g^{r_i}\right)^{\alpha_i}=1$$

$$x \sum_i \alpha_i t_i g^{\sum_i \alpha_i r_i}=1,$$

$$y_1=g^{112} x^{239}=576 \quad y_2=g^{477} x^{274}=70 \quad y_3=g^{378} x^{248}=180 \quad y_4=g^{80} x^{66}=42 \quad y_5=g^{331} x^{488}$$

$$y_1^{145} x_2^{436} y_3^{72} y_4^{73} y_5=1$$

myassignments-help数学代考价格说明

1、客户需提供物理代考的网址，相关账户，以及课程名称，Textbook等相关资料~客服会根据作业数量和持续时间给您定价~使收费透明，让您清楚的知道您的钱花在什么地方。

2、数学代写一般每篇报价约为600—1000rmb，费用根据持续时间、周作业量、成绩要求有所浮动(持续时间越长约便宜、周作业量越多约贵、成绩要求越高越贵)，报价后价格觉得合适，可以先付一周的款，我们帮你试做，满意后再继续，遇到Fail全额退款。

3、myassignments-help公司所有MATH作业代写服务支持付半款，全款，周付款，周付款一方面方便大家查阅自己的分数，一方面也方便大家资金周转，注意:每周固定周一时先预付下周的定金，不付定金不予继续做。物理代写一次性付清打9.5折。

Math作业代写、数学代写常见问题

myassignments-help擅长领域包含但不是全部:

myassignments-help服务请添加我们官网的客服或者微信/QQ，我们的服务覆盖：Assignment代写、Business商科代写、CS代考、Economics经济学代写、Essay代写、Finance金融代写、Math数学代写、report代写、R语言代考、Statistics统计学代写、物理代考、作业代写、加拿大代考、加拿大统计代写、北美代写、北美作业代写、北美统计代考、商科Essay代写、商科代考、数学代考、数学代写、数学作业代写、physics作业代写、物理代写、数据分析代写、新西兰代写、澳洲Essay代写、澳洲代写、澳洲作业代写、澳洲统计代写、澳洲金融代写、留学生课业指导、经济代写、统计代写、统计作业代写、美国Essay代写、美国代考、美国数学代写、美国统计代写、英国Essay代写、英国代考、英国作业代写、英国数学代写、英国统计代写、英国金融代写、论文代写、金融代考、金融作业代写。

Scroll to Top


text:
# Finding the prime factors of a positive number

I have an assignment to write on the standard output the prime factors of a positive number displayed in ascending order and separated by '*'. My code works, but I need help reviewing it before I submit my work. Allowed functions: write, printf, atoi.

void    find_factors(int n)
{
int i;
int separated;

i = 3;
separated = 0;
if (n <= 1)
return ;
while (n % 2 == 0)
{
if (separated)
printf("*");
printf("%d", 2);
separated = 1;
n = n / 2;
}
while (i <= n)
{
while(n % i == 0)
{
if (separated)
printf("*");
printf("%d", i);
separated = 1;
n = n / i;
}
i += 2;
}
if (n > 2)
{
if (separated)
printf("*");
printf("%d", n);
}
}

• It doesn't seem to quite work. find_factors(72); prints 2*2*2**3*3. Please test more, fix the bug and then update the question. – Edward Jun 14 '16 at 23:58
• @Edward I have updated the question and fixed the bug. I have also removed my_sqrt, my_printnbr and my_putchar functions. – Junius L. Jun 16 '16 at 13:08

1) The reasons for 2 loops while (n % 2 == 0) and while (i <= n) is to optimize division by 2 and allow the next prime candidate to be found with += 2.

As printing is a sink-hole of time, these small savings could be ignored and code changed to one loop.

int i = 2;
while (i <= n) {
while(n % i == 0) {
...
printf("%d", i);
separated = 1;
n = n / i;
}
i += i==2 ? 1 : 2;
}

2) Negative numbers are a problem and not well supported here, nor do they need to be. Recommend unsigned than int.

3) As an alternative to a flag and repeated test code for the "*", perhaps

char *separator = "";
...
while (...) {
printf("%s%d", separator, 2);
separator = "*";
...
}

4) Code fails for the following. OP did say "prime factors of a positive number", so 0 and negative numbers are excusable to some degree.

  find_factors(INT_MAX);  // infinite loop
find_factors(1);        // no output
find_factors(0);        // infinite loop
find_factors(negative)  // no output

5) Initialize at the same time as declaration.

// int i;
// int separated;
// i = 3;
// separated = 0;
int i = 3;
int separated = 0;

6) Consider bool for boolean variables

#include <stdbool.h>
// int separated = 0;
bool separated = false;

7) Wavy formatting

    if (separated)
printf("*");
printf("%d", 2);
separated = 1;
n = n / 2;

8) Careful passing a string to printf() as a format string as it might someday contain %.

// printf("*");
fputs("*", stdout);
// or
fputc('*', stdout);
//
putchar('*');

// OP did say  "write, printf, atoi.", so could use the following, which is a bit pedantic.
printf("%s", "*");

9) Efficiency. For large values of n, code does n/2 loops. Better to terminate at about the sqrt(n). At n % i time, also calculate qu = n / i. This can often be had for free, depending on the processor. Once i>qu, code is done.


text:
# Proving Hom(Q/Z, Q/Z) is isomorphic to \hat{Z}

1. Sep 7, 2010

### mebassett

Hi folks, long time reader, first time poster.

So I'm trying to prove that $\hat{Z} = \varprojlim Z/nZ$ is isomorphic to Hom(Q/Z, Q/Z).

Problem is, I have a lot of trouble describing even a single endomorphism of that torsion group (except, of course, the trivial one, that sends everything to 0.)

Q/Z can be considered as the set of all roots of unity. and I should be able to find an endomorphism on that group, just by permuting key roots of unity (simple example: {1,-1,i,-1}) But I haven't been able to generalize this for the whole thing.

I also tried a pretty naive thing, taking a \in \hat{Z}, say a=(a_1, a_2, ...) and trying to define some \theta : Q/Z \to Q/Z, with \theta (m/n) = (m * a_n) / n. which I believe defines a map from \hat{Z} into Hom(Q/Z, Q/Z), but I don't have much in the way of an inverse, especially since I can't describe anything but trivial members of Hom(Q/Z, Q/Z)

I'm aware that \hat{Z} is also the product of all the p-adic integers Z_p, but I'm having trouble proving that as well.

In any case, I'm stuck, I don't want to spend much more time on this (Because its just one small bit of a much larger project), so I thought I'd try asking the kind and clever folks here for some help.

so, Hom(Q/Z, Q/Z) is isomorphic to \hat{Z}. Any ideas on how to prove it?

Thanks.

Last edited: Sep 7, 2010
2. Sep 7, 2010

### Hurkyl

Staff Emeritus
Q/Z is an Abelian group, a.k.a. a Z-module. Thus multiplication by an integer is an endomorphism.

3. Sep 7, 2010

### mebassett

indeed, but that's hardly all endomorphisms!

4. Sep 7, 2010

### Hurkyl

Staff Emeritus
Sure; but since you had overlooked it, I thought I'd point it out and see if you got somewhere.

My first instinct on the problem is to write Q/Z as the union of all of its cyclic subgroups. I suppose that's just a convoluted way of saying you can write elements as m/n, though.

5. Sep 7, 2010

### mebassett

Thanks! actually, I think my naive approach works. if you define a reverse map like so:

given f \in End(Q/Z), define an a=(a_1, a_n, ... ) \in \prod_n Z/nZ by a_n = n f(1/n). if m|n, then we can write n=mr and mr f(1/n) - m f(1/m) is obviously divisible by m, so a meets the appropriate congruence relations to be in \hat{Z}. and its the inverse map of the one I defined above. So unless I'm missing something else, I think I have it...

6. Sep 7, 2010

### Hurkyl

Staff Emeritus
The functions theta you defined before aren't homomorphisms -- sorry, I misread and thought you had noticed that already.

7. Sep 7, 2010

### mebassett

(that plus sign was suppose to be multiplication. I corrected the error in the edit.)

they aren't? I thought I proved that for a \in \hat{Z}, \theta_a by \theta_a ( m/n ) = a_n * m/n was. Like so:

$$\theta_a (m_1 / n_1 + m_2 / n_2 ) = \theta_a ( (n_2 m_1 + n_1 m_2) / n_1 n_2) = a_{n_1 n_2} (n_2 m_1 + n_1 m_2) / n_1 n_2$$

$$\theta_a (m_1/n_1) + \theta_a(m_2 / n_2) = a_{n_1} m_1 / n_1 + a_{n_2} m_2 / n_2 = (a_{n_1} n_2 m_1 + a_{n_2} n_1 m_2) / n_1 n_2$$

now, by def of $$a \in \hat{Z}$$, we have $$a_{n_1 n_2} = q n_1 + a_{n_1} = r n_2 + a_{n_2}.$$ Or in other words,
$$a_{n_1} = a_{n_1 n_2} - q n_1$$ and $$a_{n_2} = a_{n_1 n_2} - r n_2$$.

so then $$a_{n_1} n_2 m_1 + a_{n_2} n_1 m_2 = a_{n_1 n_2} (n_2 m_1 + n_1 m_2) - n_1 n_2 (m_1 q + m_2 r)$$

divide that by $$n_1 n_2$$ and the negative term is 0 (since we're in Q/Z, the n_1*n_2 turns it into an integer and integers are modded out). And that proves its a homomorphism.

Or am I confused and/or making mistakes?

Last edited: Sep 7, 2010
8. Sep 7, 2010

### Hurkyl

Staff Emeritus
Changing the + to * changes things.

9. Sep 7, 2010

Ok. First, it shouldn't be hard to prove that hom(Q/Z, Q/Z) is isomorphic to hom(Q/Z, R/Z), which is the Pontryagin dual of the discrete group Q/Z. So it suffices to prove that Q/Z and $$\hat{\mathbb{Z}}$$ are dual to each other.

(In case you're unfamiliar with this duality: If G is a locally compact abelian topological group, let Ch(G) = hom(G, R/Z). Then Ch is a contravariant functor, and Ch2 is naturally isomorphic to the identity functor on the category of locally compact abelian topological groups; hence Ch is a duality of categories and thus interchanges limits and colimits.)

Now note:
$$\mathbb{Q}/\mathbb{Z} = \lim_{\longrightarrow} N^{-1}\mathbb{Z}/\mathbb{Z}.$$
and
$$\hat{\mathbb{Z}} = \lim_{\longleftarrow} \mathbb{Z}/N\mathbb{Z}.$$
(The direct and inverse limits are taken over N and divisibility.) It is elementary to show that Ch(N-1Z/Z) is naturally (in N) isomorphic to Z/NZ. Since Ch interchanges limits and colimits, we get the desired result.

Also, you can prove that $$\hat{\mathbb{Z}}$$ is the product of the Zp, purely by using the universal properties of limits and products, and the Chinese remainder theorem. (Show that the former satisfies the universal property of the latter.) The key is that if N = p1n1...pknk is a factorization of N into powers of distinct primes, then Z/NZ is isomorphic to Z/p1n1Z × ... × Z/pknkZ.

Let me know if anything needs clarification. I don't mind writing this stuff up in more detail. (Although I guess you need to know some terminology from category theory.)

Last edited: Sep 7, 2010
10. Sep 8, 2010

### mebassett

I've barely seen any category theory before, but its on my list of things to do. Thanks for that, you've given me another example to try to understand. :)

11. Sep 8, 2010

This article has fewer prerequisites, but it describes Ch(Q). Then Ch(Q/Z) is isomorphic to the subgroup of Ch(Q) consisting of elements with kernel containing Z, which presumably you can show is isomorphic to $$\hat{\mathbb{Z}}$$.


text:
## LESSON 1. Analysis of Statically Determinate Beams

1.1 Introduction

There are two important aspects of structural design. The first one is safety which means a structure should be able to withstand all external loads without any considerable damage or collapse. The second aspect is ‘serviceability’ which refers to the conditions (other than the strength) under which a structure is still considered useful. The primary objective of this course is to study how to determine parameters which constitute the basis of structural design both for safety and serviceability. We begin this course with a brief review of statics. In this review we discuss concept of degrees of freedom, constraints, characteristics of forces and conditions for static equilibrium.

1.2 Degrees of Freedom (DOF)

The degree of freedom of a mechanical system is the number of independent coordinates required to completely specify the configuration of the system. Motion of an object in a three-dimensional space can be completely described by three displacements (along three coordinate axes) and three rotations (about three coordinate axes) as shown in Figure 1.1a. Therefore in three-dimensional space an object has six degrees of freedom. Similarly in two dimensional plane an object has three degrees of freedom viz. two displacements along two coordinate axes and one rotation about an axis normal to the plane as shown in Figure 1.1b.

Fig. 1.1.

1.3 Force

To solve typical structural problems, we use equations involving forces or their components. Forces may consist of either a linear force that tends to produce translation or a couple that tends to produce rotation of the body on which it acts.

A system of planner forces acting on a rigid structure can always be reduced to two resultant forces (see Figure 1.2):

(a) A linear force R passing through the centre of gravity of the structure where R equals the vector sum of the linear forces.

(b) A moment M about the centre of gravity. The moment M is evaluated by summing the moments of all forces and couples acting on the structure with respect to an axis through the centre of gravity and perpendicular to the plane of the structure.

Fig. 1.2.

1.4 Supports and Support Reaction

To ensure that a structure or a structural element remains in its required position under all loading conditions, it is attached to a foundation or connected to other structural members by supports. Support constraints the motion of a structure by exerting resistive force called Support reaction. Depending on the number and type of constraints there are different kinds of supports. Characteristics of different kinds of supports in two-dimensions are summarized in Table 1.1.

Table 1.1 Support characteristics

1.5 Free Body Diagram

As a first step in the analysis of a structure, we draw a simplified sketch of the structure or a portion of the structure under consideration. A free body diagram is a pictorial device used in order to analyze the forces and moments acting on a body. This sketch, which shows the required dimensions together with all the external and internal forces acting on the structure is called free-body diagram (FBD). For instance Figure 1.3b shows the free-body diagram of the entire structure of a simply supported beam subjected to concentrated load at its midspan (Figure 1.3a). Let the beam is cut by a section mn. Figure 1.3c shows the free body diagram of the portion of the beam to the left part of the section mn.

Fig. 1.3.

1.6 Equations of Static Equilibrium

An object at rest is said to be in static equilibrium if the net forces acting on the body is zero. In three dimensions the equations of static equilibrium are as follows,

$\sum {{F_x}=0}$ ; $\sum {{F_y}=0}$ ;  $\sum {{F_z}=0}$           [Net force in any direction is zero]

$\sum {{M_x}=0}$ ;  $\sum {{M_y}=0}$ $\sum {{M_z}=0}$      [Net moment about any axis is zero]

Similarly in two dimensions the above equations become,

$\sum {{F_x}=0}$ ;     $\sum {{F_y}=0}$                          [Net force in any direction is zero]

$\sum {{M_z}=0}$                                    [Net moment about any axis is zero]

1.7 Determinate and Indeterminate Structure

A structure is said to be determinate if the equations of static equilibrium alone are sufficient to permit a complete analysis of the structure. If the structure cannot be analyzed by the equation of statics, the structure is termed as indeterminate. To analyze an indeterminate structure, additional equations considering the geometry of the deflected shape are required. This will be discussed in details in the next module. In this module we will learn several methods to analyze statically determinate beams.

Hbbeler, R. C. (2002). Structural Analysis, Pearson Education (Singapore) Pte. Ltd.,Delhi.

Jain, A.K., Punmia, B.C., Jain, A.K., (2004). Theory of Structures. Twelfth Edition, Laxmi Publications.

Menon, D.,  (2008), Structural Analysis, Narosa Publishing House Pvt. Ltd., New Delhi.

Hsieh, Y.Y., (1987), Elementry Theory of Structures , Third Ddition, Prentrice Hall.


text:
Need help with Pro75 casings.

Help Support The Rocketry Forum:

Ccolvin968

Well-Known Member
I'm trying to get the Pro75 starter Wildman Rocketry.
it says it comes with a 3g hardware set, 6g casing, 2 spacers and a wrench.
Does this mean that I need to get additional hardware?
Or can I fly anything between 3g and 6g reloads with this kit?
I just flew my L2 cert yesterday on a 54/75 adapter.
I'd like to have the hardware and casings available for pro75 reloads in the future.
If you have any other ideas or suggestions I'm all ears.

jd2cylman

Still not Carl... ;-)
TRF Supporter
I'm trying to get the Pro75 starter Wildman Rocketry.
it says it comes with a 3g hardware set, 6g casing, 2 spacers and a wrench.
Does this mean that I need to get additional hardware?
Or can I fly anything between 3g and 6g reloads with this kit?
I just flew my L2 cert yesterday on a 54/75 adapter.
I'd like to have the hardware and casings available for pro75 reloads in the future.
If you have any other ideas or suggestions I'm all ears.
This will set me back $700 and I just want to be sure I'm being smart about this. Thanks! So, with the 3 grain case, you can use 3 grain reloads(obviously), then use one spacer to fly 2 grain reloads, and use 2 spacers to fly 1 grain reloads (Only AT has those currently). The same holds for the 6 grain case. One spacer and 5 grain reloads, two spacers and 4 grain reloads. So, with 2 cases and 2 spacers, you can fly the whole range of reloads. Ccolvin968 Well-Known Member Okay, awesome! So it's exactly the same as all of the other starter kits. Just wanted to be sure before I bought. I'll check out Sunward, thanks Bat. Now the hard part... Saving the pennies! jd2cylman Still not Carl... ;-) TRF Supporter Just an FYI, it appears to be about$50 cheaper at Sunward than Wildman's club price.
Well, crap. Not sure where I was going with this, so...

michigander

Well-Known Member
4 grain and 6xl set would fly anything CTI 75mm

watch the yard sale section, I picked up new 4 grain set with 2 spacers $285.00 shipped Ccolvin968 Well-Known Member JD2, your reply was very helpful! Michigander, I'll do that. Thank you! WILDMANRS Sponsor TRF Sponsor TRF Supporter I'm trying to get the Pro75 starter Wildman Rocketry. it says it comes with a 3g hardware set, 6g casing, 2 spacers and a wrench. Does this mean that I need to get additional hardware? Or can I fly anything between 3g and 6g reloads with this kit? I just flew my L2 cert yesterday on a 54/75 adapter. I'd like to have the hardware and casings available for pro75 reloads in the future. If you have any other ideas or suggestions I'm all ears. This will set me back$700 and I just want to be sure I'm being smart about this.
Thanks!
I will also do this set oint: with the 6xl and 4g case if you like.

Ccolvin968

Well-Known Member
Like I said, it'll be a while before I can drop $600-$700 on the 75 starter set.
It seems like formula and diapers come before rocketry items. Haha!

Are you saying that you'd be able to do the 6XLg and the 4g starter kit for \$700?
I looked at Wildman first before anywhere else.
Thanks!
If this will get the thread locked, please feel free to send me a PM.


text:
# Is energy discrete [duplicate]

It is often stated that because the energy in an em wave is $E=hf$, the energy comes only as multiples of $h$, ie quantized. But we know that $f$ is a real number, and you could have fractions of one Hertz. The difference in energy of two such waves can be a fraction of $h$ in this case. Is this a correct thinking. I can accept that absorption and emission of energy is quantized, but this is not the same thing- as in this case the quantization is a property of the material not the wave.


text:
# How to label chapters/sections/remarks/etc. with symbols

I am writing a thesis in report class, and I would like to have something like the following format.

Part I: Introduction

Chapter 1: Some history

Chapter 2: Some literature

Chapter 3: Some more waffly stuff

Chapter $\spadesuit$: Statement of the main results

Part II: The meaty stuff

Chapter 4: Proof of Theorem $\spadesuit$.1

etc. etc.

Does anyone know how to create a chapter with sections labelled via a symbol, such as the $\spadesuit$ symbol, so Chapter $\spadesuit$ with Section $\spadesuit$.1, Section $\spadesuit$.2, etc. and Theorem $\spadesuit$.1 etc. and to have this chapter appear like that in the TOC?

Many thanks! A.

• I am not sure what you need, but hope you may expect as \renewcommand{\thechapter}{\arabic{chapter}.$\spadesuit$} – MadyYuvi Aug 13 at 13:35
• I am afraid that running this just inserted spades all throughout my document – Aerinmund Fagelson Aug 13 at 14:46

You can redefine the way the chapter counter is printed (i.e., the \thechapter macro) within the special chapter, and restore it afterwards. Note that the counter itself is still numeric, so if you want to continue numbering following the previous normal chapter then you need to decrease the chapter counter by one.

MWE:

\documentclass{report}
\usepackage{amsthm}
\newtheorem{theorem}{Theorem}[chapter]
\begin{document}
\tableofcontents
\part{Introduction}
\chapter{Some history}
\chapter{Some literature}
\chapter{Some more waffly stuff}

\let\theoldchapter\thechapter
\def\thechapter{$\spadesuit$}
\chapter{Statement of the main results}
\section{Result section}
\begin{theorem}
Waffles are tasty
\label{thm:waffles}
\end{theorem}
\let\thechapter\theoldchapter


text:
# Dropping OPTIONAL blocks from SPARQL CONSTRUCT queries

And retrieving those triples much, much faster.

While preparing a demo for the upcoming Taxonomy Boot Camp conference, I hit upon a trick for revising SPARQL CONSTRUCT queries so that they don’t need OPTIONAL blocks. As I wrote in the new “Query Efficiency and Debugging” chapter in the second edition of Learning SPARQL, “Academic papers on SPARQL query optimization agree: OPTIONAL is the guiltiest party in slowing down queries, adding the most complexity to the job that the SPARQL processor must do to find the relevant data and return it.” My new trick not only made the retrieval much faster; it also made it possible to retrieve a lot more data from a remote endpoint.

First, let’s look at a simple version of the use case. DBpedia has a lot of SKOS taxonomy data in it, and at Taxonomy Boot Camp I’m going to show how you can pull down and use that data. Now, imagine that a little animal taxonomy like the one shown in the illustration here is stored on an endpoint and I want to write a query to retrieve all the triples showing preferred labels and “has broader” values up to three levels down from the Mammal concept, assuming that the taxonomy’s structure uses SKOS to represent its structure. The following query asks for all three levels of the taxonomy below Mammal, but it won’t get the whole taxonomy:

PREFIX skos: <http://www.w3.org/2004/02/skos/core#>
CONSTRUCT {
?level1 skos:prefLabel ?level1label .
?level2 skos:broader ?level1 ;
skos:prefLabel ?level2label .
?level3 skos:broader ?level2 ;
skos:prefLabel ?level3label .
}
WHERE {
?level1 skos:broader v:Mammal ;
skos:prefLabel ?level1label .
?level2 skos:broader ?level1 ;
skos:prefLabel ?level2label .
?level3 skos:broader ?level2 ;
skos:prefLabel ?level3label .
}

As with any SPARQL query, it’s only going to return triples for which all the triple patterns in the WHERE clause match. While Horse may have a broader value of Mammal and therefore match the triple pattern {?level1 skos:broader v:Mammal}, there are no nodes that have Horse as a broader value, so there will be no match for {?level2 skos:broader v:Horse}. So, the Horse triples won’t be in the output. The same thing will happen with the Cat triples; only the Dog ones, which go down three levels below Mammal, will match the graph pattern in the WHERE clause above.

If we want a CONSTRUCT query that retrieves all the triples of the subtree under Mammal, we need a way to retrieve the Horse and Cat concepts and any descendants they have, even if they have no descendants, and OPTIONAL makes this possible. The following will do this:

PREFIX skos: <http://www.w3.org/2004/02/skos/core#>
CONSTRUCT {
?level1 skos:prefLabel ?level1label .
?level2 skos:broader ?level1 ;
skos:prefLabel ?level2label .
?level3 skos:broader ?level2 ;
skos:prefLabel ?level3label .
}
WHERE {
?level1 skos:broader v:Mammal ;
skos:prefLabel ?level1label .
OPTIONAL {
?level2 skos:broader ?level1 ;
skos:prefLabel ?level2label .
}
OPTIONAL {
?level3 skos:broader ?level2 ;
skos:prefLabel ?level3label .
}
}

The problem: this doesn’t scale. When I sent a nearly identical query to DBpedia to ask for the triples representing the hierarchy three levels down from <http://dbpedia.org/resource/Category:Mammals>, it timed out after 20 minutes, because the two OPTIONAL graph patterns gave DBpedia too much work to do.

As a review, let’s restate the problem: we want the identified concept and the preferred labels and broader values of concepts up to three levels down from that concept, but without using the OPTIONAL keyword. How can we do this?

By asking for each level in a separate query. When I split the DBpedia version of the query above into the following three queries, each retrieved its data in under a second, retrieving a total of 2,597 triples representing a taxonomy of 1,107 concepts:

# query 1
PREFIX skos: <http://www.w3.org/2004/02/skos/core#>
CONSTRUCT {
<http://dbpedia.org/resource/Category:Mammals> a skos:Concept .
?level1 a skos:Concept ;
skos:broader <http://dbpedia.org/resource/Category:Mammals> ;
skos:prefLabel ?level1label .
}
WHERE {
?level1 skos:broader <http://dbpedia.org/resource/Category:Mammals> ;
skos:prefLabel ?level1label .
}

# query 2
PREFIX skos: <http://www.w3.org/2004/02/skos/core#>
CONSTRUCT {
?level2 a skos:Concept ;
skos:broader ?level1 ;
skos:prefLabel ?level2label .
}
WHERE {
?level1 skos:broader <http://dbpedia.org/resource/Category:Mammals> .
?level2 skos:broader ?level1 ;
skos:prefLabel ?level2label .
}

# query 3
PREFIX skos: <http://www.w3.org/2004/02/skos/core#>
CONSTRUCT {
?level3 a skos:Concept ;
skos:broader ?level2 ;
skos:prefLabel ?level3label .
}
WHERE {
?level2 skos:broader/skos:broader <http://dbpedia.org/resource/Category:Mammals> .
?level3 skos:broader ?level2 ;
skos:prefLabel ?level3label .
}

Going from timing out after 20 minutes to successful execution in under 3 seconds is quite a performance improvement. Below, you can see how the beginning of a small piece of this taxonomy looks in TopQuadrant’s TopBraid EVN vocabulary manager. At the first level down, you can only see Afrosoricida, Australosphenida, and Bats in the picture; I then drilled down three more levels from there to show that Fictional bats has the single subcategory Silverwing.

As you can tell from the Mammals URI in the queries above, these taxonomy concepts are categories, and each category has at least one member (for example, Bats as food) in Wikipedia and is therefore represented as triples in DBpedia, ready for you to retrieve with SPARQL CONSTRUCT queries. I didn’t retrieve any instance triples here, but it’s great to know that they’re available, and that this technique for avoiding CONSTRUCT graph patterns will serve me for much more than SKOS taxonomy work.

There has been plenty of talk lately on Twitter and in blogs about how it’s not a good idea for important applications to have serious dependencies on public SPARQL endpoints such as DBpedia. (Orri Erling has one of the most level-head discussions of this that I’ve seen in SEMANTiCS 2014 (part 3 of 3): Conversations; in my posting Semantic Web Journal article on DBpedia on this blog I described a great article that lists other options.) There’s all this great data to use in DBpedia, and besides spinning up an Amazon Web Services image with your own copy of DBpedia, as Orri suggests, you can pull down the data you need to store locally when it is up. If you’re unsure about the structure and connections of the data you’re pulling down, OPTIONAL graph patterns seems like an obvious fix, but this trick for splitting up CONSTRUCT queries to avoid the use of OPTIONAL graph patterns means that you can pull down a lot more data lot more efficiently.

## Stickin’ to the UNION

October 16th update: Once I split out the pieces of the original query into separate files, it should have occurred to me to at least try joining them back up into a single query with UNION instead of OPTIONAL, but it didn’t. Luckily for me, John Walker suggested in the comments for this blog entry that I try this, so I did. It worked great, with the benefit of being simpler to read and maintain than using a collection of queries to retrieve a single set of triples. This version only took three seconds to retrieve the triples:

PREFIX skos: <http://www.w3.org/2004/02/skos/core#>
CONSTRUCT {
<http://dbpedia.org/resource/Category:Mammals> a skos:Concept .
?level1 a skos:Concept ;
skos:broader <http://dbpedia.org/resource/Category:Mammals> ;
skos:prefLabel ?level1label .
?level2 a skos:Concept ;
skos:broader ?level1 ;
skos:prefLabel ?level2label .
?level3 a skos:Concept ;
skos:broader ?level2 ;
skos:prefLabel ?level3label .

}
WHERE {
?level1 skos:broader <http://dbpedia.org/resource/Category:Mammals> ;
skos:prefLabel ?level1label .
{
?level2 skos:broader ?level1 ;
skos:prefLabel ?level2label .
}
UNION
{
?level2 skos:broader ?level1 .
?level3 skos:broader ?level2 ;
skos:prefLabel ?level3label .
}
}

There are two lessons here:

• If you’ve figured out a way to do something better, don’t be too satisfied too quickly—keep trying to make it even better.

• UNION is going to be useful in more situations than I originally thought it would.


text:
Middle Years

# 2.04 Expansion

Worksheet
The distributive law
1

A student incorrectly used the distributive property and wrote 6 \left( 7 x + 2\right) = 42 x + 2.

Explain how to correct the error.

2

Expand the following expressions:

a

5 \left(s + 7\right)

b

9 \left(5 + w\right)

c

3 \left(r - 6\right)

d

\left(y + 8\right) \times 7

e

- 8 \left(t + 10\right)

f

- 8 \left(c - 5\right)

g

- \left( y + 2 \right)

h

4 \left( 4 s + 5\right)

i

- 10 \left(8 + 3 r\right)

j

- 8 \left( - 2 t - 3\right)

k

p \left(q + 4\right)

l

9 \left(u - v\right)

m

- \left( 2 m - 3 n \right)

n

- r \left( 11 s + 13 t\right)

o

4 \left( 2 r + 3 s + 5 t\right)

p

6\left(4m+3n+5p\right)

3

Expand the following expressions:

a

6 m \left( 2 n + 3\right)

b

9 \left(v^{2} + 6\right)

c

r \left(r + 7\right)

d

6 m \left( 4 m + 7\right)

e

- 6 a \left( 2 a + 9\right)

f

4 w y \left(y + w\right)

g

4 p \left( 4 q - 3 + 6 r\right)

h

2 f \left(f - 7 g - 6 h\right)

i

- 10 \left(y^{2} + 7\right)

j

- \left( 9 - s^{3} \right)

k

r \left(s^{2} + 8\right)

l

- 10 \left(3 + 8 u^{3}\right)

m

4 s^{5} \left( 4 t^{4} - 9\right)

n

6p^3\left(2q^5-9\right)

o

9f\left(f-4g-6h\right)

p

3uv\left(v+u\right)

4

Expand and simplify the following expressions:

a

4 \left(x + 8\right) - 2

b

7 + 5 \left( 3 x + 4\right)

c

5 + 3 \left(x + 4\right)

d

8 \left( 3 x + 4\right) - 6 x

e

34 + 9 \left( 4 x - 5\right)

f

5 x - 8 \left( 2 x - 3\right)

g

9 x - 5 \left( 2 x + 3\right)

h

- 8 \left( 5 x - 7\right) - 9

i

4 y + 5 + 6 \left(y - 9\right)

j

4 \left( 5 \left(x - 3\right) + 2\right)

5

Expand and simplify the following expressions:

a

x \left(x + 4\right) + 8 \left(x + 9\right)

b

8 y^{2} - 4 y + 7 y \left(y - 5\right)

c

3 \left( 6 x - 5 y\right) - 2 \left( 9 y + 4 x\right)

d

7 \left(y + 9\right) + 5 \left(y + 6\right)

e

10 \left(x - 4\right) + 3 \left(x + 8\right)

f

5 \left(y + 7\right) - \left(y - 9\right)

g

-8 \left(x + 4\right) - 3 \left(x - 2\right)

h

11\left(a + 4\right) -6 \left(4-a \right)

i

4 u \left( 6 u + 9 v\right) - 2 u \left( 8 v + 5 u\right)

j

9w\left(8w+6z\right)-5w\left(4z+2w\right)

Applications
6

A solar energy company offers a range of solar panels, each with a power rating of \\ (m + 8) \text{ kW}, where m is the panel model number. Write an expression in terms of m for the total amount of power produced by 11 solar panels.

7

The representatives of 8 countries are attending a global summit, and each country is able to send (2 r - 3) representatives. Write an expression for the total number of representatives attending the summit.

8

A forklift operator has enough time to make 5 trips between the two ends of a warehouse. A forklift can carry (2 + 3 n^{4}) boxes at a time. Write an expression for the total number of boxes that can be carried across the warehouse.

9

Consider the rectangle shown:

Find an expression for the area of the rectangle in expanded form.

10

A rectangle is 8 \text{ m} longer than it is width. Its width is represented by the pronumeral u.

Form an expression for the area of the rectangle in expanded form.


text:
## Local factors of Tamagawa measure

This is a reference request to some computations which I hope can be found in the literature somewhere. Let G⊂GLn be a semisimple linear algebraic group over Q. The Tamagawa measure μ on the group of adelic points G(A) is uniquely determined by the product formula. Nevertheless, it can be written as a product of … Read more

## A generalized ellipse

We know that an ellipse is the locus of all point $z$ in the plane with $$|z-a|+|z-b|=\lambda$$ where $a,b$ are two given points in the plane and $\lambda$ is a constant. Now we consider the following generalization: For three given points $a,b,c \in \mathbb{R}^{2}$ define $$A_{\lambda}=\{z\in \mathbb{R}^{2} \;\text{with}\;\; |z-a|+|z-b|+|z-c|=\lambda\}$$ How is the geometric description of … Read more

## Sobolev spaces defined on non-compact Lie groups

In this post, a question was raised to discuss the generalization of Sobolev spaces on locally compact Lie groups. Now my question is whether there exists a generalization of Sobolev spaces and associated theories of the Laplace operator on noncompact Lie groups. My expectation is that the theory should be reduced to coincide with that … Read more

## Well-definedness on C∞0(Rn)C_{0}^{\infty}(\mathbb{R}^{n})

Let T be a Calderon-Zygmund operator associated to a Calderon-Zygmund kernel K∈CZKα of order α>0 and b∈BMO(Rn). Then for f∈C∞0(Rn) define[b,T](f)=b⋅Tf−T(bf). Question. Is [b,T] is well-defined on C∞0(Rn) for all b∈BMO(Rn)? Answer AttributionSource : Link , Question Author : Timothy , Answer Author : Community

## Coming up with a represenation for sum of functions in the Fourier algebra

This is my first overflow question, so let me apologize in advance if this belongs on http://math.stackexchange.com. Let G be a discrete group. Let λ:G→B(ℓ2(G)) be the left regular representation of G and A(G) the Fourier algebra of G. Given f,g∈A(G), and writing f(s)=⟨λ(s)x,y⟩,g(s)=⟨λ(s)w,z⟩ for some choice x,y,w,z∈ℓ2(G), is there a way to choose (in … Read more

## Continuous doubling weight vanishing on set of positive measure?

If I is a bounded interval in R, let 2I denote an interval with the same center point but double the length. A doubling measure on R is a (non-trivial, locally finite, Borel) measure μ such that μ(2I)≤Cμ(I) for all intervals I and some fixed constant C. A doubling weight is an L1loc function w:R→R≥0 … Read more

## Integral form of maximal function estimate on variable exponent spaces

I am trying to show an estimate of the following form: Given any p(x) such that 1<p−≤p(x)≤p+<∞ and p(⋅) is log-Holder continuous, does there exists an R0 (depending only on p(⋅), n and log-Holder continuity of p(x)) such that ∫BRM<2R(|f|)p(x)(x) dx≤C∫B2R|f(x)|p(x) dx+1 holds for every function f∈Lp(⋅)(B2R) and every R<R0. Here M<T(|f|)(x):=supr<T1|B(x,r)|∫B(x,r)|f(y)| dy EDIT: I have been informed … Read more

I am investigating the following integral $$I^*(x) = \int_{\mathbb{R}} \frac{f(y) \ln |y-x| }{|y – x|^{\mu}} \, dy$$ where $f \in L_p(\mathbb{R})$, $1 < p < q < \infty$, and $\mu = 1 + \frac{1}{q} – \frac{1}{p}$. For the integral $$I(x) = \int_{\mathbb{R}} \frac{f(y) }{|y – x|^{\mu}} \, dy$$ there … Read more