10757 - Interpreting SQL

All about problems in Volume 107. If there is a thread about your problem, please use it. If not, create one with its number in the subject.

Moderator: Board moderators

Post Reply
Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

10757 - Interpreting SQL

Post by Destination Goa »

I am surprised there is still no thread about this 0.0% problem (though there were some submissions).

The description is more than perfect, except one issue which is serious:
The rest of the input file contains the query.
I think authors initially had their tests in separate files and just created multi-test for UVA engine. But how should I spot the end of 'SELECT' clause? Should I investigate its syntax, which is always broken if number is appended?

Did authors try to solve it with multi-test or just contatenated their correct outputs as well?

I'd like to see clarification on this issue before starting writing this. It's too tremendous problem to start even with such practically resolvable issues.
To be the best you must become the best!
Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa »

Also authors might have adopted their solution to multi-test but forgot that end-of-file is not actually end-of-file with multi-test. Then they will output whatever their parser will do with incorrect request. I don't think this is the case, but anyway... That zero scares me too much to spend days with this problem, so I'd like to check everything :-?
To be the best you must become the best!
Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa »

Another issue:
The operations are executed from left to right; i.e., `a AND b OR c' means `(a AND b) OR c'.
AND/OR are not operations, <, <=, >, >=, ... are operations as defined in grammar. Also a AND b OR c is bad example. What should be equal parenthesis setup for 1<2 OR 2>3 AND 4>5 OR "a"=name AND "q"="w"?
To be the best you must become the best!
Larry
Guru
Posts: 647
Joined: Wed Jun 26, 2002 10:12 pm
Location: Hong Kong and New York City
Contact:

Post by Larry »

I don't see why boolean operations shouldn't be considered operations..
Destination Goa
Experienced poster
Posts: 123
Joined: Thu Feb 10, 2005 4:46 am

Post by Destination Goa »

Larry,

Because they are not defined as operations under that grammar (read problem statement). Operations under that grammar are [in]equality operators, but AND/OR are just separators in terms of that grammar.
To be the best you must become the best!
G
New poster
Posts: 4
Joined: Sun Nov 28, 2004 12:45 pm

Invalid input syntax?

Post by G »

I was trying to solve problem #10757 and failed. While checking my work I found a strange input. My program runs through the first test case and when it tries to read in the number of tables in the second test case, it fails. Cheking what character my program gets, I found a '@' character. This character cannot appear in the input (except in string constants). I carefully checked my program if it handles string constants correctly, and I do not see a bug (anyway: my program works well on program-generated really long test cases too). Could you, please, check if the input syntax is correct?

I do not know what multi-test is. May be my problem is related to this. Can someone clear me up on this? On the other hand: I wrote my program to recognize the end of the SQL statement, altough a usual ';' at the end would have helped.

One more note: the problem description does not state what one should do when "select *" is used with more than one table. I assume, that all columns in the tables appearing in from part should be presented, and their order is the order of the tables in the from part and the order of the columns in the table description. Also, in this case there may be at most 100 columns selected (10 tables in the from part and 10 columns/table), as there is no limit stated in the description for this case. Am I right in this?
G
New poster
Posts: 4
Joined: Sun Nov 28, 2004 12:45 pm

Dirty tricks

Post by G »

I am finished with this problem. It turns out:
1. There is at least one line of garbage characters between the test cases.
2. There are column names like "where" which is prohibited in all SQL servers I know. Certainly it is not stated in the problem description, but still I think it is a very dirty trick.

Geza
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Re: Dirty tricks

Post by Martin Macko »

It's very sad that problemsetters haven't corrected this problem yet :cry:
thurbo
New poster
Posts: 9
Joined: Wed Apr 05, 2006 2:00 pm
Location: Stockholm, Sweden

Post by thurbo »

Just my 2 cents:

After reading this thread I decided to give it try (very tempting with its 0% solutions) and just started with a program that just reads input (not that trivial).
Anyway, if I would find an error in the input the program would hang itself and that is exactly what I got (TLE) which does not surprise me after reading this thread. Still, it could be an error in my program (it happened before :D) and maybe we should post some test inputs just to check eachother?
This one should be easy:

4

3
Person 2 2
PID I
PName S
1 ABCDEF
2 ZYXWVU
Book 2 5
BID I
BName S
1 TheQuickBrownFox
2 HelloWorld
3 JumpJumpJump
4 RockTheWorld
5 LazyDog
Borrows 2 6
FKPID I
FKBID I
1 1
1 3
2 1
2 4
2 5
1 2
SELECT *
FROM (Borrows INNER JOIN Book ON FKBID = BID) INNER JOIN Person ON FKPID = PID
WHERE PName = "ABCDEF"

3
Person 2 2
PID I
PName S
1 ABCDEF
2 ZYXWVU
Book 2 5
BID I
BName S
1 TheQuickBrownFox
2 HelloWorld
3 JumpJumpJump
4 RockTheWorld
5 LazyDog
Borrows 2 6
FKPID I
FKBID I
1 1
1 3
2 1
2 4
2 5
1 2
SELECT *
FROM Person INNER JOIN (Borrows INNER JOIN Book ON FKBID = BID) ON PID = FKPID
WHERE PName = "ABCDEF"

1
WHERE 2 3
FROM I
ORDER S
1 XXX
2 YYY
3 ZZZ
SELECT FROM, ORDER
FROM WHERE
WHERE FROM = 2 AND ORDER = 3 OR 0 = 1

4
AccountInfo 4 3
Account I
LastName S
FirstName S
Balance I
1 Ivanov Petr 2500
2 Petrov Ivan 2000
3 Ivanov Ivan 3000
AccountTransfers 3 4
From I
To I
Amount I
1 2 1000
2 3 2000
3 1 3000
2 1 10
OrigAccountInfo 4 3
OAccount I
OLastName S
OFirstName S
OBalance I
1 Ivanov Petr 2500
2 Petrov Ivan 2000
3 Ivanov Ivan 3000
OrigAccountTransfers 3 4
OFrom I
OTo I
OAmount I
1 2 1000
2 3 2000
3 1 3000
2 1 10
SELECT *
FROM
(AccountInfo INNER JOIN AccountTransfers ON Account=From)
INNER JOIN
(OrigAccountInfo INNER JOIN OrigAccountTransfers ON OAccount=OFrom)
ON LastName = OLastName
WHERE FirstName<>"Petr"
ORDER BY LastName DESCENDING, Amount
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

thurbo wrote:

Code: Select all

1
WHERE 2 3
FROM I
ORDER S
1 XXX
2 YYY
3 ZZZ
SELECT FROM, ORDER
  FROM WHERE
  WHERE FROM = 2 AND ORDER = 3 OR 0 = 1
Imho, according to the problem description, the column ORDER should be compared to a string constant instead of to a number:

Code: Select all

  WHERE FROM = 2 AND ORDER = "3" OR 0 = 1
My WA's output is as follows:

Code: Select all

6 3
FKPID
FKBID
BID
BName
PID
PName
1 1 1 TheQuickBrownFox 1 ABCDEF
1 3 3 JumpJumpJump 1 ABCDEF
1 2 2 HelloWorld 1 ABCDEF

6 3
PID
PName
FKPID
FKBID
BID
BName
1 ABCDEF 1 1 1 TheQuickBrownFox
1 ABCDEF 1 3 3 JumpJumpJump
1 ABCDEF 1 2 2 HelloWorld

2 0
FROM
ORDER

14 6
Account
LastName
FirstName
Balance
From
To
Amount
OAccount
OLastName
OFirstName
OBalance
OFrom
OTo
OAmount
2 Petrov Ivan 2000 2 1 10 2 Petrov Ivan 2000 2 3 2000
2 Petrov Ivan 2000 2 1 10 2 Petrov Ivan 2000 2 1 10
2 Petrov Ivan 2000 2 3 2000 2 Petrov Ivan 2000 2 3 2000
2 Petrov Ivan 2000 2 3 2000 2 Petrov Ivan 2000 2 1 10
3 Ivanov Ivan 3000 3 1 3000 1 Ivanov Petr 2500 1 2 1000
3 Ivanov Ivan 3000 3 1 3000 3 Ivanov Ivan 3000 3 1 3000
thurbo
New poster
Posts: 9
Joined: Wed Apr 05, 2006 2:00 pm
Location: Stockholm, Sweden

Post by thurbo »

Martin Macko wrote:
thurbo wrote:

Code: Select all

1
WHERE 2 3
FROM I
ORDER S
1 XXX
2 YYY
3 ZZZ
SELECT FROM, ORDER
  FROM WHERE
  WHERE FROM = 2 AND ORDER = 3 OR 0 = 1
Imho, according to the problem description, the column ORDER should be compared to a string constant instead of to a number:

Code: Select all

  WHERE FROM = 2 AND ORDER = "3" OR 0 = 1
You are absolutely right!
Martin Macko wrote:

Code: Select all

6 3
FKPID
FKBID
BID
BName
PID
PName
1 1 1 TheQuickBrownFox 1 ABCDEF
1 3 3 JumpJumpJump 1 ABCDEF
1 2 2 HelloWorld 1 ABCDEF

6 3
PID
PName
FKPID
FKBID
BID
BName
1 ABCDEF 1 1 1 TheQuickBrownFox
1 ABCDEF 1 3 3 JumpJumpJump
1 ABCDEF 1 2 2 HelloWorld

2 0
FROM
ORDER

14 6
Account
LastName
FirstName
Balance
From
To
Amount
OAccount
OLastName
OFirstName
OBalance
OFrom
OTo
OAmount
2 Petrov Ivan 2000 2 1 10 2 Petrov Ivan 2000 2 3 2000
2 Petrov Ivan 2000 2 1 10 2 Petrov Ivan 2000 2 1 10
2 Petrov Ivan 2000 2 3 2000 2 Petrov Ivan 2000 2 3 2000
2 Petrov Ivan 2000 2 3 2000 2 Petrov Ivan 2000 2 1 10
3 Ivanov Ivan 3000 3 1 3000 1 Ivanov Petr 2500 1 2 1000
3 Ivanov Ivan 3000 3 1 3000 3 Ivanov Ivan 3000 3 1 3000
Your output looks right to me. I could not compare it to mine as I don't have any. I thought I would test reading input first before I would continue...
tobby
Learning poster
Posts: 98
Joined: Fri Dec 30, 2005 3:31 pm

Post by tobby »

thurbo wrote:Anyway, if I would find an error in the input the program would hang itself and that is exactly what I got (TLE) which does not surprise me after reading this thread.
Maybe you guys should inform the judge admins (through Bugs and Suggestions forum maybe) about the mistakes of this problem?
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

tobby wrote:Maybe you guys should inform the judge admins (through Bugs and Suggestions forum maybe) about the mistakes of this problem?
I have just post it to that forum. Let's wait what admins/problemsetters will do about it. :)
Martin Macko
A great helper
Posts: 481
Joined: Sun Jun 19, 2005 1:18 am
Location: European Union (Slovak Republic)

Post by Martin Macko »

The judge's IOs for this problem have been changed and my solution has got ACed. Could somebody, please, try to solve it, so we know if there are any more bugs in the IOs?

Note, that there may be table and column names such as where, from, select, etc. Also note, that the queries are not guaranteed to have spaces anywhere else than between names.
Post Reply

Return to “Volume 107 (10700-10799)”